Name
Title | ||
|---|---|---|
Smallest domination number and largest independence number of graphs and forests with given degree sequence |
Abstract | ||
|---|---|---|
For a sequence d of nonnegative integers, let G(d) and F(d) be the sets of all graphs and forests with degree sequence d, respectively. Let min(d)=min{(G):GG(d)}, max(d)=max{(G):GG(d)}, minF(d)=min{(F):FF(d)}, and maxF(d)=max{(F):FF(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 GG(d) with min(d)=(G), and F,FF(d) with minF(d)=(F) and maxF(d)=(F) 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 minF(d) and maxF(d). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/jgt.22189 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
annihilation number,clique,degree sequence,dominating set,forest realization,independent set,realization | Graph,Dominating set,Independence number,Combinatorics,Clique,Independent set,Degree (graph theory),Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
88.0 | 1.0 | 0364-9024 |
Citations | PageRank | References |
4 | 0.55 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Gentner | 1 | 22 | 4.46 |
| Michael A. Henning | 2 | 1865 | 246.94 |
| Dieter Rautenbach | 3 | 946 | 138.87 |