L-Distance Total Domination and a Polynomial Algorithm in Block Graphs

Abstract

In this paper, we extend the concept of k-distance total domination to the concept of L-distance total domination, which is to find a minimum vertex set

D\subseteq V

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$D\subseteq V$$\end{document}

such that each vertex v of the graph G is at a distance

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$0<d(v,u)\leqslant a_v$$\end{document}

from some vertex

u\in D

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$u\in D$$\end{document}

, where

a_v

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$a_v$$\end{document}

is an arbitrary positive integer assigned to v, and

L=\{a_v|v\in V(G)\}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$L=\{a_{v}|~v\in V(G)\}$$\end{document}

. We then compute the exact values of the L-distance total domination numbers of paths and cycles. Finally, by constructing a proper order of the vertices and using a labeling method, we provide an

O(n^2)

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^2)$$\end{document}

time algorithm to find a minimum L-distance total dominating set of a block graph, a superclass of trees. Since k-distance total domination is a special form of L-distance total domination, the above algorithm can also determine the k-distance total domination number of a block graph.

Keywords

L-distance total domination / Polynomial time algorithm / Labeling method / Block graph / Tree / 05C69 / 05C85

References

[1] Bertossi AA. Dominating sets for split and bipartite graphs. Inf. Process. Lett., 1984, 19(1): 37-40

[2] Booth KS, Johnson JH. Dominating sets in chordal graphs. SIAM J. Comput., 1982, 11(1): 191-199

[3] Chang, G.J.: Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Appl. Math. 22, 21–34 (1988)

[4] Chang GJ, Nemhauser GL. The k\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$k$$\end{document}-domination and k\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$k$$\end{document}-stability problems on sun-free chordal graphs. SIAM J. Algebraic Discrete Methods, 1984, 5(3): 332-345

[5] Cockayne EJ, Goodman S, Hedetniemi ST. A linear algorithm for the domination number of a tree. Inf. Process. Lett., 1975, 4: 41-44

[6] Fricke, G.H., Henning, M.A., Oellermann, O.R., Swart, H.C.: An algorithm to find two distance domination parameters in a graph. Discrete Appl. Math. 68(1/2), 85–91 (1996)

[7] Haynes TW, Hedetniemi ST, Slater PJ. Fundamentals of Domination in Graphs, 1998, New York. Marcel Dekker

[8] Henning, M.A.: Chapter 12: Distance domination in graphs. In: Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds) Domination in Graphs: Advanced Topics. Marcel Dekker, Inc., New York (1997)

[9] Henning, M.A., Oellermann, O.R., Swart, H.C.: Bounds on distance domination parameters. J. Combin. Inf. Syst. Sci. 16(1), 11–18 (1991)

[10] Henning, M.A., Oellermann, O.R., Swart, H.C.: The diversity of domination. Discrete Math. 161(1/2), 161–173 (1996)

[11] Laskar R, Pfaff J, Hedetniemi SM, Hedetniemi ST. On the algorithmic complexity of total domination. SIAM J. Algebraic Discrete Methods, 1984, 5: 420-425

[12] McRae, A.A.: Generalizing NP-completeness proofs for bipartite and chordal graphs. Ph.D. Thesis, Clemson University (1994)

[13] Mitchell SL, Hedetniemi ST. Edge domination in trees. Congr. Number, 1977, 19: 489-509

[14] Slater PJ. R-domination in graphs. J. Assoc. Comput. Mach., 1976, 23: 446-450

[15] Zhao YC, Miao LY, Liao ZH. A linear-time algorithm for 2-step domination in block graphs. J. Math. Res. Appl., 2015, 35(3): 285-290

[16] Zhao YC, Shan EF. An efficient algorithm for distance total domination in block graphs. J. Comb. Optim., 2016, 31: 372-381

Funding

Natural Science Foundation of Guangxi Zhuang Autonomous Region(2023JJA110023)

RIGHTS & PERMISSIONS

Shanghai University