Total domination in cubic Knödel graphs

Document Type : Original paper

Authors

1 Shahed University

2 Departtment of Mathematics, University of Mazandaran

3 Shahrood University of Technology

4 Tafresh University

Abstract

A subset $D$ of vertices of a graph $G$ is a dominating set if for each $u\in V(G) \setminus D$, $u$ is adjacent to some vertex $v\in D$. The domination number, $\gamma(G)$ of $G$, is the minimum cardinality of a dominating set of $G$. A set $D\subseteq V(G)$ is a total dominating set if for each $u\in V(G)$, $u$ is adjacent to some vertex $v\in D$. The total domination number, $\gamma_{t}(G)$ of $G$, is the minimum cardinality of a total dominating set of $G$. For an even integer $n\ge 2$ and $1\le \Delta \le \lfloor\log_2n\rfloor$, a Kn\"odel graph $W_{\Delta,n}$ is a $\Delta$-regular bipartite graph of even order $n$, with vertices $(i,j)$, for $i=1,2$ and $0\le j\le \frac{n}{2}-1$, where for every $j$, $0\le j\le \frac{n}{2}-1$, there is an edge between vertex $(1, j)$ and every vertex $(2,(j+2^k-1)$ mod $\frac{n}{2}$), for $k=0,1,\dots,\Delta-1$. In this paper, we determine the total domination number in $3$-regular Kn\"odel graphs $W_{3,n}$.

Keywords

Main Subjects

References

[1] J.-C. Bermond, H.A. Harutyunyan, A.L. Liestman, and S. Perennes, A note on the dimensionality of modified Knödel graphs, Int. J. Foundations Comput. Sci. 8 (1997), no. 2, 109–116.
[2] G. Fertin and A. Raspaud, Families of graphs having broadcasting and gossiping properties, International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, 1998, pp. 63–77.
[3] G. Fertin and A. Raspaud, A survey of Knödel graphs, Discrete Appl. Math. 137 (2004), no. 2, 173–196.
[4] P. Fraigniaud and J.G. Peters, Minimum linear gossip graphs and maximal linear (δ, k)-gossip graphs, Networks 38 (2001), no. 3, 150–162.
[5] H. Grigoryan and H.A. Harutyunyan, Broadcasting in the Knödel graph, Ninth International Conference on Computer Science and Information Technologies, IEEE, 2013, pp. 1–6.
[6] H. Grigoryan and H.A. Harutyunyan, The shortest path problem in the Kn¨odel graph, J. Discrete Algorithms 31 (2015), 40–47.
[7] H.A. Harutyunyan, Multiple message broadcasting in modified Knödel graph, SIROCCO, vol. 7, 2000, pp. 157–165.
[8] H.A. Harutyunyan, Minimum multiple message broadcast graphs, Networks 47 (2006), no. 4, 218–224.
[9] H.A. Harutyunyan, An efficient vertex addition method for broadcast networks, Internet Math. 5 (2008), no. 3, 211–225.
[10] H.A. Harutyunyan and Z. Li, A new construction of broadcast graphs, Discrete Appl. Math. 280 (2020), 144–155.
[11] H.A. Harutyunyan and A.L. Liestman, More broadcast graphs, Discrete Appl. Math. 98 (1999), no. 1-2, 81–102.
[12] H.A. Harutyunyan and A.L. Liestman, Upper bounds on the broadcast function using minimum dominating sets, Discrete Math. 312 (2012), no. 20, 2992–2996.
[13] H.A. Harutyunyan and C.D. Morosan, On the minimum path problem in Knödel graphs, Networks 50 (2007), no. 1, 86–91.
[14] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs- Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[15] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, 2013.
[16] L. Khachatrian and H. Harutounian, On optimal broadcast graphs, Fourth International Colloquium on Coding Theory, Dilijan, Armenia, 1991, pp. 36–40.
[17] W. Knödel, New gossips and telephones, Discrete Math. 13 (1975), no. 1, 95.
[18] D.A. Mojdeh, S.R. Musawi, and E. Nazari, Domination critical Knödel graphs, Iran J. Sci. Technol. Trans. Sci. 43 (2019), no. 5, 2423–2428.
[19] S. Varghese, A. Vijayakumar, and A.M. Hinz, Power domination in Knödel graphs and Hanoi graphs, Discuss. Math. Graph Theory 38 (2018), no. 1, 63–74.
[20] F. Xueliang, X. Xu, Y. Yuansheng, and X. Feng, On the domination number of Knödel graph W(3, n), International Journal of Pure and Applied Mathematics 50 (2009), no. 4, 553–558.
 
 
Communications in Combinatorics and Optimization
Volume 6, Issue 2
December 2021
Pages 221-230

Files

Share

How to cite

Statistics