Total domination number of middle graphs
Abstract
A total dominating set of a graph G with no isolated vertices is a subset S of the vertex set such that every vertex of G is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set.
In this paper, we study the total domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph. We also compute the total domination number of the middle graph of some known families of graphs explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the total domination number of middle graphs.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.19
References
M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Applied Mathematics, 161 (2013), 466–546.
J. A. Bondy and U. S. R. Murty, Graph theory, Graduate texts in mathematics, vol. 244, Springer Science and Media, 2008.
E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs, Networks, 10 (1980), 211–219.
T. Hamada and I. Yoshimura, Traversability and connectivity of the middle graph of a graph, Discrete Mathematics, 14 (1976) 247–255.
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
M. A. Henning and A. Yeo, Total domination in graphs, Springer Monographs in Mathematics, 2013.
F. Kazemnejad and S. Moradi, Total domination number of central graphs, Bulletin of the Korean Mathematical Society, 56 (4) (2019), 1059–1075.
F. Kazemnejad, B. Pahlavsay, E. Palezzato and M. Torielli, Domination number of middle graphs. ArXiv:2008.02975.
F. Kazemnejad, B. Pahlavsay, E. Palezzato and M. Torielli, Total dominator coloring number of middle graphs. To appear in Discrete Mathematics, Algorithms and Applications, 2022.
E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly, 63 (1956), 175–177.
L. Ouldrabah, M. Blidia and A. Bouchou, Roman domination in oriented trees, Electronic Journal of Graph Theory and Applications, 9 (1) (2021), 95–103.
B. Pahlavsay, E. Palezzato and M. Torielli, 3-tuple total domination number of rook’s graphs. Discussiones Mathematicae Graph Theory, 42 (2022), 15–37
B. Pahlavsay, E. Palezzato and M. Torielli, Domination in latin square graphs. Graphs and Combinatorics, 37 (3) (2021), 971–985.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.