Trees with equal domination and tree-free domination numbers

Teresa W. Haynes; Michael A. Henning

doi:10.1016/S0012-365X(01)00053-X

Trees with equal domination and tree-free domination numbers

Teresa W. Haynes, Michael A. Henning

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

1 Citation (Scopus)

Abstract

The tree-free domination number y(G; -Fk), k ≥ 2, of a graph G is the minimum cardinality of a dominating set S in G such that the subgraph (S) induced by S contains no tree on k vertices as a (not necessarily induced) subgraph (equivalently, each component of (S) has cardinality less than k). When k = 2, the tree-free domination number is the independent domination number. We obtain a characterization of trees with equal domination and tree-free domination numbers. This generalizes a result of Cockayne et al. (A characterisation of (y,i)-trees. J. Graph Theory 34(4) (2000) 277-292).

Original language	English
Pages (from-to)	93-102
Number of pages	10
Journal	Discrete Mathematics
Volume	242
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(01)00053-X
Publication status	Published - 1 Jun 2002
Externally published	Yes

Keywords

Domination number
Independent domination number
Tree
Tree-free domination number

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(01)00053-X

Cite this

@article{41c66f2574794f1f82a70228dbf1d8ff,

title = "Trees with equal domination and tree-free domination numbers",

abstract = "The tree-free domination number y(G; -Fk), k ≥ 2, of a graph G is the minimum cardinality of a dominating set S in G such that the subgraph (S) induced by S contains no tree on k vertices as a (not necessarily induced) subgraph (equivalently, each component of (S) has cardinality less than k). When k = 2, the tree-free domination number is the independent domination number. We obtain a characterization of trees with equal domination and tree-free domination numbers. This generalizes a result of Cockayne et al. (A characterisation of (y,i)-trees. J. Graph Theory 34(4) (2000) 277-292).",

keywords = "Domination number, Independent domination number, Tree, Tree-free domination number",

author = "Haynes, \{Teresa W.\} and Henning, \{Michael A.\}",

year = "2002",

month = jun,

day = "1",

doi = "10.1016/S0012-365X(01)00053-X",

language = "English",

volume = "242",

pages = "93--102",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Trees with equal domination and tree-free domination numbers

AU - Haynes, Teresa W.

AU - Henning, Michael A.

PY - 2002/6/1

Y1 - 2002/6/1

N2 - The tree-free domination number y(G; -Fk), k ≥ 2, of a graph G is the minimum cardinality of a dominating set S in G such that the subgraph (S) induced by S contains no tree on k vertices as a (not necessarily induced) subgraph (equivalently, each component of (S) has cardinality less than k). When k = 2, the tree-free domination number is the independent domination number. We obtain a characterization of trees with equal domination and tree-free domination numbers. This generalizes a result of Cockayne et al. (A characterisation of (y,i)-trees. J. Graph Theory 34(4) (2000) 277-292).

AB - The tree-free domination number y(G; -Fk), k ≥ 2, of a graph G is the minimum cardinality of a dominating set S in G such that the subgraph (S) induced by S contains no tree on k vertices as a (not necessarily induced) subgraph (equivalently, each component of (S) has cardinality less than k). When k = 2, the tree-free domination number is the independent domination number. We obtain a characterization of trees with equal domination and tree-free domination numbers. This generalizes a result of Cockayne et al. (A characterisation of (y,i)-trees. J. Graph Theory 34(4) (2000) 277-292).

KW - Domination number

KW - Independent domination number

KW - Tree

KW - Tree-free domination number

UR - https://www.scopus.com/pages/publications/33750806013

U2 - 10.1016/S0012-365X(01)00053-X

DO - 10.1016/S0012-365X(01)00053-X

M3 - Article

AN - SCOPUS:33750806013

SN - 0012-365X

VL - 242

SP - 93

EP - 102

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Trees with equal domination and tree-free domination numbers

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this