Largest domination number and smallest independence number of forests with given degree sequence

Michael Gentner; Michael A. Henning; Dieter Rautenbach

doi:10.1016/j.dam.2016.01.040

Largest domination number and smallest independence number of forests with given degree sequence

Michael Gentner, Michael A. Henning, Dieter Rautenbach

Mathematics and Applied Mathematics

Ulm University

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

For a sequence d of non-negative integers, let F(d) be the set of all forests whose degree sequence is d. We present closed formulas for γmaxF(d)=max{γ(F):FϵF(d)} and αminF(d)=min{α(F):FϵF(d)} where γ(F) and α(F) are the domination number and the independence number of a forest F, respectively.

Original language	English
Pages (from-to)	181-187
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	206
DOIs	https://doi.org/10.1016/j.dam.2016.01.040
Publication status	Published - 19 Jun 2016

Keywords

Clique
Degree sequence
Dominating set
Forest realization
Independent set
Realization

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2016.01.040

Cite this

@article{de131c51fecd49d59fdb071a8c355c98,

title = "Largest domination number and smallest independence number of forests with given degree sequence",

abstract = "For a sequence d of non-negative integers, let F(d) be the set of all forests whose degree sequence is d. We present closed formulas for γmaxF(d)=max{γ(F):FϵF(d)} and αminF(d)=min{α(F):FϵF(d)} where γ(F) and α(F) are the domination number and the independence number of a forest F, respectively.",

keywords = "Clique, Degree sequence, Dominating set, Forest realization, Independent set, Realization",

author = "Michael Gentner and Henning, {Michael A.} and Dieter Rautenbach",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2016",

month = jun,

day = "19",

doi = "10.1016/j.dam.2016.01.040",

language = "English",

volume = "206",

pages = "181--187",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Largest domination number and smallest independence number of forests with given degree sequence

AU - Gentner, Michael

AU - Henning, Michael A.

AU - Rautenbach, Dieter

PY - 2016/6/19

Y1 - 2016/6/19

N2 - For a sequence d of non-negative integers, let F(d) be the set of all forests whose degree sequence is d. We present closed formulas for γmaxF(d)=max{γ(F):FϵF(d)} and αminF(d)=min{α(F):FϵF(d)} where γ(F) and α(F) are the domination number and the independence number of a forest F, respectively.

AB - For a sequence d of non-negative integers, let F(d) be the set of all forests whose degree sequence is d. We present closed formulas for γmaxF(d)=max{γ(F):FϵF(d)} and αminF(d)=min{α(F):FϵF(d)} where γ(F) and α(F) are the domination number and the independence number of a forest F, respectively.

KW - Clique

KW - Degree sequence

KW - Dominating set

KW - Forest realization

KW - Independent set

KW - Realization

UR - http://www.scopus.com/inward/record.url?scp=84975707274&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2016.01.040

DO - 10.1016/j.dam.2016.01.040

M3 - Article

AN - SCOPUS:84975707274

SN - 0166-218X

VL - 206

SP - 181

EP - 187

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Largest domination number and smallest independence number of forests with given degree sequence

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this