Document Open Access Logo

Minimum Neighboring Degree Realization in Graphs and Trees

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.10.pdf
  • Filesize: 0.79 MB
  • 15 pages

Document Identifiers

Author Details

Amotz Bar-Noy
  • City University of New York (CUNY), NY, USA
Keerti Choudhary
  • Tel Aviv University, Israel
Avi Cohen
  • Weizmann Institute of Science, Rehovot, Israel
David Peleg
  • Weizmann Institute of Science, Rehovot, Israel
Dror Rawitz
  • Bar-Ilan University, Ramat-Gan, Israel

Funding

US-Israel BSF grant 2018043; ARL Network Science CTA W911NF-09-2-0053.

Cite AsGet BibTex

Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz. Minimum Neighboring Degree Realization in Graphs and Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.10

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph realization
  • neighborhood profile
  • graph algorithms
  • degree sequences

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Martin Aigner and Eberhard Triesch. Realizability and uniqueness in graphs. Discrete Mathematics, 136:3-20, 1994. Google Scholar
  2. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Realizability of graph specifications: Characterizations and algorithms. In 25th SIROCCO, LNCS, pages 3-13, 2018. Google Scholar
  3. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently realizing interval sequences. In 30th ISAAC, pages 47:1-47:15, 2019. Google Scholar
  4. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Graph profile realizations and applications to social networks. In 13th WALCOM, LNCS, pages 1-12, 2019. Google Scholar
  5. Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Graph realizations: Maximum degree in vertex neighborhoods. In Proc. SWAT, 2020. Google Scholar
  6. Michael D. Barrus and Elizabeth A. Donovan. Neighborhood degree lists of graphs. Discrete Mathematics, 341(1):175-183, 2018. Google Scholar
  7. Joseph K. Blitzstein and Persi Diaconis. A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Mathematics, 6(4):489-522, 2011. Google Scholar
  8. Sheshayya A. Choudum. A simple proof of the Erdös-Gallai theorem on graph sequences. Bull. Austral. Math. Soc., 33(1):67-70, 1991. Google Scholar
  9. Brian Cloteaux. Fast sequential creation of random realizations of degree sequences. Internet Mathematics, 12(3):205-219, 2016. Google Scholar
  10. Paul Erdös and Tibor Gallai. Graphs with prescribed degrees of vertices [hungarian]. Matematikai Lapok, 11:264-274, 1960. Google Scholar
  11. S.L. Feld. Why your friends have more friends than you do. Amer. J. Sociology, 96:1464-1477, 1991. Google Scholar
  12. S. Louis Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph - I. SIAM J. Appl. Math., 10(3):496-506, 1962. Google Scholar
  13. Peter L. Hammer, Toshihide Ibaraki, and Bruno Simeone. Threshold sequences. SIAM J. Algebraic Discrete Methods, 2(1):39-49, 1981. Google Scholar
  14. V. Havel. A remark on the existence of finite graphs. Casopis Pest. Mat., 80:477-480, 1955. Google Scholar
  15. P.J. Kelly. A congruence theorem for trees. Pacific J. Math., 7:961-968, 1957. Google Scholar
  16. Milena Mihail and Nisheeth Vishnoi. On generating graphs with prescribed degree sequences for complex network modeling applications. 3rd ARACNE, 2002. Google Scholar
  17. Elchanan Mossel and Nathan Ross. Shotgun assembly of labeled graphs. CoRR, abs/1504.07682, 2015. URL: http://arxiv.org/abs/1504.07682.
  18. Peter V. O'Neil. Ulam’s conjecture and graph reconstructions. Amer. Math. Monthly, 77:35-43, 1970. Google Scholar
  19. Gerard Sierksma and Han Hoogeveen. Seven criteria for integer sequences being graphic. J. Graph Theory, 15(2):223-231, 1991. Google Scholar
  20. Amitabha Tripathi and Himanshu Tyagi. A simple criterion on degree sequences of graphs. Discrete Applied Mathematics, 156(18):3513-3517, 2008. Google Scholar
  21. Regina Tyshkevich. Decomposition of graphical sequences and unigraphs. Discrete Mathematics, 220(1-3):201-238, 2000. Google Scholar
  22. S.M. Ulam. A collection of mathematical problems. Wiley, 1960. Google Scholar
  23. D.L. Wang and D.J. Kleitman. On the existence of n-connected graphs with prescribed degrees (n > 2). Networks, 3:225-239, 1973. Google Scholar
  24. N.C. Wormald. Models of random regular graphs. Surveys in Combin., 267:239-298, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact