Smallest domination number and largest independence number of graphs and forests with given degree sequence

Michael Gentner, Michael A. Henning, Dieter Rautenbach

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

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 languageEnglish
Pages (from-to)131-145
Number of pages15
JournalJournal of Graph Theory
Volume88
Issue number1
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Smallest domination number and largest independence number of graphs and forests with given degree sequence'. Together they form a unique fingerprint.

Cite this