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

Abstract: For a sequence <italic>d</italic> of nonnegative integers, let G ( d ) and F ( d ) be the sets of all graphs and forests with degree sequence <italic>d</italic>, respectively. Let γ min ( d ) = min { γ ( G ) : G ∈ G ( d ) }, α max ( d ) = max { α ( G ) : G ∈ G ( d ) }, γ min F ( d ) = min { γ ( F ) : F ∈ F ( d ) }, and α max F ( d ) = max { α ( F ) : F ∈ F ( d ) } where γ ( G ) is the domination number and α ( G ) is the independence number of a graph <italic>G</italic>. 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 γ min ( d ) = γ ( G ), and F γ , F α ∈ F ( d ) with γ min F ( d ) = γ ( F γ ) and α max F ( d ) = α ( F α ) that have strong structural properties. This leads to an efficient algorithm to determine γ min ( d ) for every given degree sequence <italic>d</italic> with bounded entries as well as closed formulas for γ min F ( d ) and α max F ( d ). [ABSTRACT FROM AUTHOR]