2015/07/16 by Michael Gentner, Gentner, Michael, Michael A. Henning +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1507.04647
openalex publication_date 2015/07/16 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
For a sequence d of non-negative integers, let cal G(d) and cal\nF(d) be the sets of all graphs and forests with degree sequence d,\nrespectively. Let \γ\min(d)=\min \γ(G):G\∈ cal G(d) ,\n\α\max(d)=\max \α(G):G\∈ cal G(d) , \γ\min cal\nF(d)=\min \γ(F):F\∈ cal F(d) , and \α\max cal\nF(d)=\max \α(F):F\∈ cal F(d) where \γ(G) is the domination\nnumber and \α(G) is the independence number of a graph G. Adapting\nresults of Havel and Hakimi, Rao showed in 1979 that \α\max(d) can be\ndetermined in polynomial time.\n We establish the existence of realizations G\∈ cal G(d) with\n\γ\min(d)=\γ(G), and F\γ,F\α\∈ cal F(d) with\n\γ\min cal F(d)=\γ(F\γ) and \α\max cal\nF(d)=\α(F\α) that have strong structural properties. This leads to\nan efficient algorithm to determine \γ\min(d) for every given degree\nsequence d with bounded entries as well as closed formulas for\n\γ\min cal F(d) and \α\max cal F(d).\n