Strong equality of domination parameters in trees

DOI10.1016/S0012-365X(02)00451-XMaRDI QIDQ1861245zbMATH OpenFDO

Authors Teresa W. Haynes, Michael A. Henning, Peter Slater

Publication date 16 March 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00451-X

zbMATH Keywords

characterizationdomination numberindependent dominationtotal dominationtrees

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Review text

Let \(\gamma(G)\) denote the domination number of graph \(G\), i.e., the minimum cardinality of a dominating vertex set in \(G\), let \(i(G)\) denote the independent domination number of \(G\), i.e., the minimum cardinality of an independent dominating vertex set in \(G\), let \(\gamma_t(G)\) denote the total domination number of graph \(G\), i.e., the minimum cardinality of a totally dominating vertex set in \(G\) (here, the vertices in the dominating set must dominate each other), and let \(\gamma_p(G)\) denote the paired-domination number of graph \(G\), i.e., the minimum cardinality of a dominating vertex set \(S\) in \(G\) such that \(G[S]\) contains at least one perfect matching. This paper gives a constructive characterization of the trees \(T\) for which, first, \(\gamma(T)= i(T)\), second, \(\gamma(T)= \gamma_t(T)\), and third, \(\gamma(T)= \gamma_p(T)\).

Recommendations

• scientific article; zbMATH DE number 2108130
• A characterization of trees with equal domination and total domination numbers.
• scientific article; zbMATH DE number 4055636
• Dominating sets and independent sets in a tree.
• Domination number, independent domination number and 2-independence number in trees

Cited in

(25)

• Constructive characterizations of \( (\gamma_p,\gamma)\)-and \( (\gamma_p, \gamma_{pr})\)-trees
• Changing and unchanging of the domination number of a graph: path addition numbers
• Perfectly relating the domination, total domination, and paired domination numbers of a graph
• Some notes on the isolate domination in graphs
• Construction of trees and graphs with equal domination parameters
• Trees with equal domination and restrained domination numbers
• Strong equality of upper domination and independence in trees
• Strong equality of Roman and weak Roman domination in trees
• Graphs with strong equality on paired and double domination numbers
• Dominating sets and independent sets in a tree.
• Vertices contained in all minimum paired-dominating sets of a tree
• scientific article; zbMATH DE number 4055636 (Why is no real title available?)
• An inequality chain of domination parameters for trees
• Characterizations of trees with equal domination parameters
• scientific article; zbMATH DE number 1507962 (Why is no real title available?)
• A Gallai-type equality for the total domination number of a graph
• Strong equality of domination parameters in graphs
• Triangulations and equality in the domination chain
• Unicyclic graphs with strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers
• A note on an induced subgraph characterization of domination perfect graphs
• Trees with equal domination and tree-free domination numbers
• Complexity of comparing the domination number to the independent domination, connected domination, and paired domination numbers
• Strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers in trees
• \(\gamma\)-excellent, critically dominated, end-dominated, and dot-critical trees are equivalent
• A characterization of \((2\gamma ,\gamma _{\text p})\)-trees

This page was built for publication: Strong equality of domination parameters in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1861245)