License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.10
URN: urn:nbn:de:0030-drops-128765
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12876/
Bar-Noy, Amotz ;
Choudhary, Keerti ;
Cohen, Avi ;
Peleg, David ;
Rawitz, Dror
Minimum Neighboring Degree Realization in Graphs and Trees
Abstract
We study a graph realization problem that pertains to degrees in vertex neighborhoods. The classical problem of degree sequence realizability asks whether or not a given sequence of n positive integers is equal to the degree sequence of some n-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles.
In this paper we introduce and explore the minimum degrees in vertex neighborhood profile as it is one of the most natural extensions of the classical degree profile to vertex neighboring degree profiles. Given a graph G = (V,E), the min-degree of a vertex v ∈ V, namely MinND(v), is given by min{deg(w) ∣ w ∈ N[v]}. Our input is a sequence σ = (d_?^{n_?}, ⋯ , d₁^{n₁}), where d_{i+1} > d_i and each n_i is a positive integer. We provide some necessary and sufficient conditions for σ to be realizable. Furthermore, under the restriction that the realization is acyclic, i.e., a tree or a forest, we provide a full characterization of realizable sequences, along with a corresponding constructive algorithm.
We believe our results are a crucial step towards understanding extremal neighborhood degree relations in graphs.
BibTeX - Entry
@InProceedings{barnoy_et_al:LIPIcs:2020:12876,
author = {Amotz Bar-Noy and Keerti Choudhary and Avi Cohen and David Peleg and Dror Rawitz},
title = {{Minimum Neighboring Degree Realization in Graphs and Trees}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {10:1--10:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12876},
URN = {urn:nbn:de:0030-drops-128765},
doi = {10.4230/LIPIcs.ESA.2020.10},
annote = {Keywords: Graph realization, neighborhood profile, graph algorithms, degree sequences}
}
|
Keywords: |
|
Graph realization, neighborhood profile, graph algorithms, degree sequences |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
