×

zbMATH — the first resource for mathematics

Edge weighting functions on semitotal dominating sets. (English) Zbl 1441.05171
Summary: A set \(S\) of vertices in an isolate-free graph \(G\) is a semitotal dominating set of \(G\) if it is a dominating set of \(G\) and every vertex in \(S\) is within distance 2 of another vertex of \(S\). The semitotal domination number is the minimum cardinality of a semitotal dominating set of \(G\), and is bounded below by the domination number and bounded above by the total domination number, arguably the two most important domination parameters. The upper semitotal domination number, \(\Gamma_{t2}(G)\), of \(G\) is the maximum cardinality of a minimal semitotal dominating set in \(G\). If \(G\) is a connected graph with minimum degree \(\delta \geq 1\) and of order \(n \geq \delta + 2\), then we show that \(\Gamma_{t2}(G) \leq n - \delta \), and that this bound is sharp for every fixed \(\delta \geq 1\). Using edge weighting functions on semitotal dominating sets we show that if we impose a regularity condition on a graph, then this upper bound on the upper semitotal domination number can be greatly improved. We prove that if \(G\) is a 2-regular graph on \(n\) vertices with no \(K_3\)-component, then \(\Gamma_{t2}(G) \leq \frac{4}{7}n\), with equality if and only if every component of \(G\) is a cycle of length congruent to zero modulo 7. For \(k \geq 3\), we prove that if \(G\) is a \(k\)-regular graph on \(n\) vertices, then \(\Gamma_{t2}(G) \leq \frac{1}{2}n\), and we characterize the infinite families of graphs that achieve equality in this bound.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brešar, B, Vizing-like conjecture for the upper domination of Cartesian products of graphs—the proof, Electron. J. Combin., 12, 6, (2005) · Zbl 1074.05065
[2] Dorbec, P; Henning, MA; Rall, DF, On the upper total domination number of Cartesian products of graphs, J. Combin. Optim., 16, 68-80, (2008) · Zbl 1157.05042
[3] Fang, Q, On the computational complexity of upper total domination, Discr. Appl. Math., 136, 13-22, (2004) · Zbl 1032.05096
[4] Favaron, O; Henning, MA, Upper total domination in claw-free graphs, J. Graph Theory, 44, 148-158, (2003) · Zbl 1028.05078
[5] Grobler, PJP; Mynhardt, CM, Vertex criticality for upper domination and irredundance, J. Graph Theory, 37, 205-212, (2001) · Zbl 0992.05057
[6] Gutin, G; Zverovich, VE, Upper domination and upper irredundance perfect graphs, Discr. Math., 190, 95-105, (1998) · Zbl 0956.05077
[7] Goddard, W; Henning, MA; McPillan, CA, Semitotal domination in graphs, Utilitas Math., 94, 67-81, (2014) · Zbl 1300.05220
[8] Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998) · Zbl 0890.05002
[9] Henning, MA; Marcon, AJ, On matching and semitotal domination in graphs, Discr. Math., 324, 13-18, (2014) · Zbl 1284.05196
[10] Henning, M.A., Marcon, A.J.: Semitotal Domination in Graphs: Partition and Algorithmic Results. Utilitas Math. (Accepted) · Zbl 1284.05196
[11] Henning, MA; Marcon, AJ, Vertices contained in all or in no minimum semitotal dominating set of a tree, Discuss. Math. Graph Theory, 36, 71-93, (2016) · Zbl 1329.05232
[12] Henning, MA; Marcon, AJ, Semitotal domination in claw-free cubic graphs, Ann. Comb., 20, 799-813, (2016) · Zbl 1354.05107
[13] Henning, MA; Löwenstein, C, Locating-total domination in claw-free cubic graphs, Discr. Math., 312, 3107-3116, (2012) · Zbl 1252.05162
[14] Henning, M.A., Yeo, A.: Total domination in graphs (Springer Monographs in Mathematics) (2013). ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online) · Zbl 1408.05002
[15] Marcon, A.J.: Semitotal domination in graphs. PhD dissertation, University of Johannesburg (2015) · Zbl 1354.05107
[16] Southey, J; Henning, MA, Edge weighting functions on dominating sets, J. Graph Theory, 72, 346-360, (2013) · Zbl 1261.05080
[17] Zverovich, IE; Zverovich, VE, A semi-induced subgraph characterization of upper domination perfect graphs, J. Graph Theory, 31, 29-49, (1999) · Zbl 0920.05060
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.