×

The existence problem of \(k\mathrm{-}\gamma_t\)-critical graphs. (English) Zbl 1331.05175

Summary: A set \(S\) of vertices in graph \(G\) is a total dominating set of \(G\) if every vertex of \(G\) is adjacent to some vertex in \(S\). The minimum cardinality of a total dominating set of \(G\) is the total domination number \(\gamma_t(G)\). A graph \(G\) with no isolated vertex is total domination vertex critical if for any vertex \(v\) of \(G\) that is not adjacent to a vertex of degree one, the total domination number of \(G\backslash\{v\}\) is less than the total domination number of \(G\). We call such graphs \(\gamma_t\)-critical. If such a graph \(G\) has total domination number \(k\), we call it \(k\mathrm{-}\gamma_t\)-critical. It is well known from M. Y. Sohn et al. [Discrete Appl. Math. 159, No. 1, 46–52 (2011; Zbl 1208.05103)] that the only remaining open cases are \(\Delta(G)=5,7,9\) for \(k=5\) and \(\Delta(G)=7,9,11\) for \(k=7\). In this paper, the existence of \(\Delta(G)=5,7\) for \(k=5\) are presented and the existence of \(\Delta(G)=7,9\) for \(k=7\) are presented.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C22 Signed and weighted graphs

Citations:

Zbl 1208.05103
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. American Elsevier, New York, Macmillan, London (1976) · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[2] Goddard, W., Haynes, T.W., Henning, M.A., van der Merwe, L.C.: The diameter of total domination vertex critical graphs. Discrete Math. 286, 255-C261 (2004) · Zbl 1055.05113 · doi:10.1016/j.disc.2004.05.010
[3] Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998) · Zbl 0890.05002
[4] Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1997) · Zbl 0883.00011
[5] Henning, M.A., Rad, N.J.: On total domination vertex critical graphs of high connectivity. Discrete Appl. Math. 157(8), 1969-1973 (2009) · Zbl 1197.05107 · doi:10.1016/j.dam.2008.12.009
[6] Mojdeh, D.A., Rad, N.J.: On the total domination critical graphs. Electron. Notes Discrete Math. 24, 89-92 (2006) · Zbl 1202.05102 · doi:10.1016/j.endm.2006.06.015
[7] Mojdeh, D.A., Rad, N.J.: On an open problem concerning total domination critical graphs. Expositiones Math. 25, 175-179 (2007) · Zbl 1119.05081 · doi:10.1016/j.exmath.2006.10.001
[8] Sohn, M.Y., Kim, D., Kwon, Y.S., Lee, J.: On the existence problem of the total domination vertex critical graphs. Discrete Appl. Math. 159, 46-52 (2011) · Zbl 1208.05103 · doi:10.1016/j.dam.2010.09.004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.