Total domination supercritical graphs with respect to relative complements (Q1850074)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Total domination supercritical graphs with respect to relative complements |
scientific article |
Statements
Total domination supercritical graphs with respect to relative complements (English)
0 references
2 December 2002
0 references
The authors define a graph \(G\) to be total domination \(k\)-supercritical relative to \(K_{s,s}\), if \(G\) is a connected spanning subgraph of \(K_{s,s}\) and \(\gamma_t(G+e)=\gamma_t(G)-2=k-2\) for every edge \(e\in E(K_{s,s})\setminus E(G)\) where \(\gamma_t\) denotes the total domination number. After proving some basic properties of such graphs related to vertex degrees, neighbourhoods and the diameter, the authors prove the existence of such graphs for every even \(k\geq 4\) and diameters \(k=1\) and \(5\). They characterize total domination \(k\)-supercritical graphs relative to \(K_{s,s}\) for \(k=4\), \(k=6\) and diameter \(4\) and \(k=6\) and diameter \(5\). The paper closes with a series of open problems.
0 references
total domination
0 references
critical graph
0 references
relative complement
0 references