## 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)}, γf_{min}(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 γ^{f}_{min} and α^{f}_{max}.

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