Total domination critical and stable graphs upon edge removal
type: Item
instance of: scholarly article
title: Total domination critical and stable graphs upon edge removal
zbMATH Open document ID: 1237.05148
author: Wyatt J. Desormeaux
author: Teresa W. Haynes
author: Michael A. Henning
published in: Discrete Applied Mathematics
publication date: 2010-11-05T00:00:00Z
review text: A set of vertices in a graph \(G\) ia a total dominating set, in short \(TDS\), of \(G\) if every vertex of \(G\) is adjacent to some vertex in \(S\). The minimum cardinality of a \(TDS\) is the total domination number \(\gamma_t(G)\) of \(G\). A \(TDS\) of \(G\) of cardinality \(\gamma_t(G)\) is called a \(\gamma_t\)-set. A graph \(G\) is total domination edge critical or \(\gamma_t\)-critical if the removal of any arbitrary edge increases the total domination number. In this paper the authors prove that a graph \(G\) is a \(\gamma_t\)-critical graph if and only if it is a non-trivial star, or a double star or can be obtained from a subdivided star \(K_{1,k}^*\), where \(k \geq 2\), by adding zero or more pendant edges to the non-leaf vertices of \(K_{1,k}^*\). A graph is total domination edge stable or \(\gamma_t\)-stable if the removal of any arbitrary edge has no effect on the total domination number. The authors investigate several properties of \(\gamma_t\)-stable graphs such as if \(G\) is \(\gamma_t\)-stable then \(\delta(G) \geq 2\) and \(G\) has at least two distinct \(\gamma_t\)-sets. They also prove that there is no forbidden subgraph characterization for \(\gamma_t\)-stable graphs. They also characterize bipartite \(\gamma_t\)-stable graphs. For a connected graph \(G\), they establish the relation \(\mathrm{diam}(G) \leq \gamma_t(G) + 2c(G) - 1\), where \(c(G)\) is the minimum number of components in the subgraph induced by a \(\gamma_t\)-set and obtain infinite families of graphs which satisfy equality in the above relation.
reviewed by: Aparna Lakshmanan S.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5810753
zbMATH Keywords: total domination edge critical
zbMATH Keywords: total domination edge stable
zbMATH Keywords: total dominating set
zbMATH Keywords: total domination number
MaRDI profile type: Publication
full work available at URL: j.dam.2010.06.003
OpenAlex ID: W2162243707
cites work: Q3070325
cites work: Total domination in graphs
cites work: The diameter of total domination vertex critical graphs
cites work: Q4443245
cites work: Q4552196
cites work: Q4368728
cites work: Q4368729
cites work: Q5460882
cites work: Q5461547
cites work: A survey of selected recent results on total domination in graphs
cites work: Graphs with large total domination number
cites work: Q3410859
cites work: Q4228229
cites work: Q4933935
cites work: Total Domination Edge Critical Graphs with Maximum Diameter
cites work: Q5466050
cites work: Q5755104
cites work: Q3626179
cites work: Q5431231
DOI: 10.1016/J.DAM.2010.06.003
description: scientific article; zbMATH DE number 5810753