×

zbMATH — the first resource for mathematics

A Vizing-type result for semi-total domination. (English) Zbl 1407.05172
Summary: A set of vertices \(S\) in a simple isolate-free graph \(G\) is a semi-total dominating set of \(G\) if it is a dominating set of \(G\) and every vertex of \(S\) is within distance 2 of another vertex of \(S\). The semi-total domination number of \(G\), denoted by \(\gamma_{t 2}(G)\), is the minimum cardinality of a semi-total dominating set of \(G\). In this paper, we study semi-total domination of Cartesian products of graphs. Our main result establishes that for any graphs \(G\) and \(H\), \(\gamma_{t 2}(G \square H) \geq \frac{1}{3} \gamma_{t 2}(G) \gamma_{t 2}(H)\).

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Brešar, B., Improving the clark-suen bound on the domination number of the cartesian product of graphs, Discrete Math., 340, 2398-2401, (2017) · Zbl 1367.05155
[2] Brešar, B.; Dorbec, P.; Goddard, W.; Hartnell, B.; Henning, M.; Klavžar, S.; Rall, D., Vizing’s conjecture: a survey and recent results, J. Graph Theory, 69, 1, 46-76, (2012) · Zbl 1234.05173
[3] Brešar, B.; Hartinger, T. R.; Kos, T.; Milanič, M., On total domination in the cartesian product of graphs, Discuss. Math. Graph Theory, 38, 963-976, (2018) · Zbl 1392.05086
[4] Brešar, B.; Henning, M. A.; Rall, D. F., Paired-domination of cartesian products of graphs and rainbow domination, Electron. Notes Discrete Math., 22, 233-237, (2005) · Zbl 1200.05154
[5] Clark, W. E.; Suen, S., An inequality related to vizing’s conjecture, Electron. J. Combin., 7, N4, (2000) · Zbl 0947.05056
[6] Goddard, W.; Henning, M. A.; McPillan, C. A., Semitotal domination in graphs, Util. Math., 94, 67-81, (2014) · Zbl 1300.05220
[7] Henning, M. A., Edge weighting functions on semitotal dominating sets, Graphs Combin., 33, 2, 403-417, (2017) · Zbl 1441.05171
[8] Henning, M. A.; Marcon, A. J., On matching and semitotal domination in graphs, Discrete Math., 324, 13-18, (2014) · Zbl 1284.05196
[9] Henning, M. A.; Marcon, A. J., Semitotal domination in claw-free cubic graphs, Ann. Comb., 20, 4, 799-813, (2016) · Zbl 1354.05107
[10] Henning, M. A.; Marcon, A. J., Vertices contained in all or in no minimum semitotal dominating set of a tree, Discuss. Math. Graph Theory, 36, 1, 71-93, (2016) · Zbl 1329.05232
[11] Henning, M. A.; Marcon, A. J., Semitotal domination in graphs: partition and algorithmic results, Util. Math., (2018), in press · Zbl 1396.05085
[12] Henning, M. A.; Rall, D. F., On the total domination number of cartesian products of graphs, Graphs Combin., 21, 63-69, (2005) · Zbl 1062.05109
[13] M.A. Henning, A. Yeo, Total domination in graphs, in: Springer Monographs in Mathematics, 2013, ISBN-13: 978-1461465249.
[14] Ho, P. T., A note on the total domination number, Util. Math., 77, 97-100, (2008) · Zbl 1161.05056
[15] Lou, Y.; Hou, X., Total domination in the cartesian product of a graph and \(k_2\) or \(c_n\), Util. Math., 83, 313-322, (2010) · Zbl 1242.05208
[16] Marcon, A. J., Semitotal Domination in Graphs, (2015), University of Johannesburg, (Ph.D. dissertation) · Zbl 1284.05196
[17] Vizing, V. G., The cartesian product of graphs, Vycisl. Sistemy, 9, 30-43, (1963)
[18] Zhu, E.; Shao, Z.; Xu, J., Semitotal domination in claw-free cubic graphs, Graphs Combin., (2017) · Zbl 1386.05146
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.