Abstract
For a sequence d of nonnegative integers, let d and G(d) be the sets of all graphs and forests with degree sequence d, respectively. Let F(d), Let γmin(d) = min{ γ (G) :G ∈ g(d)}, α max(d) = max{α (G) : G ∈ g(d)}, γfmin(d) = min{γ (f) : f ∈ f(d)}, and αfmax(d) = max{α (f) : f ∈ f(d)}, where γ(G) is the domination number and α(G) is the independence number of a graph G. Adapting results of Havel and Hakimi, Rao showed in 1979 that α max(d) can be determined in polynomial time. We establish the existence of realizations G ∈ g(d) with γfmin(d), and α max(d) with α max(d) and α max(d) that have strong structural properties. This leads to an efficient algorithm to determine γmin(d) for every given degree sequence d with bounded entries as well as closed formulas for γfmin and αfmax.
Original language | English |
---|---|
Pages (from-to) | 131-145 |
Number of pages | 15 |
Journal | Journal of Graph Theory |
Volume | 88 |
Issue number | 1 |
DOIs | |
Publication status | Published - May 2018 |
Keywords
- 05C07
- 05C69
- MSC2010: 05C05
- annihilation number
- clique
- degree sequence
- dominating set
- forest realization
- independent set
- realization
ASJC Scopus subject areas
- Geometry and Topology