Total domination subdivision numbers of trees
type: Item
instance of: scholarly article
title: Total domination subdivision numbers of trees
zbMATH Open document ID: 1054.05076
author: Teresa W. Haynes
author: Michael A. Henning
author: Lora Hopkins
published in: Discrete Mathematics
publication date: 2004-11-22T00:00:00Z
review text: The total domination subdivision number \(\text{ sd}_{\gamma_t}(G)\) of a graph \(G\) is the minimum number of edges whose subdivision increases the total domination number \({\gamma_t}(G)\) of \(G\). \textit{T. W. Haynes} et al. [J. Comb. Math. Comb. Comput. 44, 115--128 (2003; Zbl 1020.05048)] have shown that \(1\leq \text{ sd}_{\gamma_t}(T)\leq 3\) for any tree \(T\). In the present paper the authors provide a constructive characterization of the family \({\mathcal F}\) of trees \(T\) with \(\text{ sd}_{\gamma_t}(T)=3\). The family \({\mathcal F}\) consists of labeled trees, contains a path of order \(6\) whose vertices have labels \(c,b,a,a,b,c\) and is closed under the two operations \({\mathcal T}_1\) and \({\mathcal T}_2\) where \({\mathcal T}_1\) consists of adding a path of order \(3\) labeled \(a,b,c\) to a tree \(T\in {\mathcal F}\) and joining the vertex labeled \(a\) to a vertex labeled \(a\) in \(T\) and \({\mathcal T}_2\) consists of adding a path of order \(4\) labeled \(a,a,b,c\) to a tree \(T\in {\mathcal F}\) and joining the endvertex labeled \(a\) to a vertex labeled \(b\) or \(c\) in \(T\).
reviewed by: Dieter Rautenbach
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 2117309
zbMATH Keywords: total domination
zbMATH Keywords: total domination subdivision number
MaRDI profile type: Publication
full work available at URL: j.disc.2004.06.004
OpenAlex ID: W2054191869
cites work: Total domination in graphs
cites work: Domination and independence subdivision numbers of graphs
cites work: Q4368728
cites work: Q4368729
cites work: Q4405924
DOI: 10.1016/J.DISC.2004.06.004
Recommended article: Q3514292
Recommended article: Domination subdivision numbers of trees
Recommended article: Q5503357
Recommended article: Q5449154
Recommended article: Q5442384
Recommended article: Bounding the total domination subdivision number of a graph in terms of its order
Recommended article: Trees whose 2-domination subdivision number is 2
Recommended article: An upper bound for the total domination subdivision number of a graph
Recommended article: On two conjectures concerning total domination subdivision number in graphs
Recommended article: Domination subdivision and domination multisubdivision numbers of graphs
description: scientific article; zbMATH DE number 2117309