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
Go to the corresponding LIPIcs Volume Portal

Bar-Noy, Amotz ; Choudhary, Keerti ; Cohen, Avi ; Peleg, David ; Rawitz, Dror

Minimum Neighboring Degree Realization in Graphs and Trees

LIPIcs-ESA-2020-10.pdf (0.8 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI