An algorithm to check the equality of total domination number and double of domination number in graphs

ISSN: 1300-0098
Yayın Aralığı: Yılda 6 Sayı
Yayıncı: TÜBİTAK

In graph theory, domination number and its variants such as total domination number are studied by many authors. Let the domination number and the total domination number of a graph G without isolated vertices be γ(G) and γt(G), respectively. Based on the inequality γt(G) ≤ 2γ(G), we investigate the graphs satisfying the upper bound, that is, graphs G with γt(G) = 2γ(G). In this paper, we present some new properties of such graphs and provide an algorithm which can determine whether γt(G) = 2γ(G) or not for a family of graphs not covered by the previous results in the literature.

PDF

___

[1] Bahadır S, Gözüpek D. On a class of graphs with large total domination number. Discrete Mathematics & Theoretical Computer Science 2018; 20 (1): 23. doi: 10.23638/DMTCS-20-1-23
[2] Bollobás B, Cockayne EJ. (1979). Graph-theoretic parameters concerning domination, independence, and irredundance. Journal of Graph Theory 1979; 3: 241-249.
[3] Cyman J, Dettlaff M, Henning MA, Lemańska M, Raczek J. Total domination versus domination in cubic graphs. Graphs and Combinatorics 2018; 34 (1): 261-276.
[4] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Company, 1979, pp. 641-650.
[5] Henning MA. (2001). Trees with large total domination number. Utilitas Mathematica 2001; 60: 99-106.
[6] Hou X, Lu Y, Xu X. A characterization of (γt, 2γ)-block graphs. Utilitas Mathematica 2010; 82: 155-159.
[7] Pfaff J, Laskar R, Hedetniemi S. NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical Report 428. Clemson, SC, USA: Clemson University, 1983.