آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 123 |
| تعداد مقالات | 1,577 |
| تعداد مشاهده مقاله | 1,706,457 |
| تعداد دریافت فایل اصل مقاله | 1,589,741 |
Total domination in cubic Knödel graphs | ||
| Communications in Combinatorics and Optimization | ||
| دوره 6، شماره 2، اسفند 2021، صفحه 221-230 اصل مقاله (417.76 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2020.26793.1143 | ||
| نویسندگان | ||
| Nader Jafari Rad* 1؛ Doost Ali Mojdeh2؛ Reza Musawi3؛ E. Nazari4 | ||
| 1Shahed University | ||
| 2Departtment of Mathematics, University of Mazandaran | ||
| 3Shahrood University of Technology | ||
| 4Tafresh University | ||
| چکیده | ||
| 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}$. | ||
| کلیدواژهها | ||
| Knodel graph؛ domination number؛ total domination number؛ Pigeonhole Principle | ||
| مراجع | ||
|
[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.
| ||
|
آمار تعداد مشاهده مقاله: 939 تعداد دریافت فایل اصل مقاله: 1,381 |
||