Diameter of General Knödel Graphs

• Autorzy: Musawi Seyed Reza , Nazari Esmaeil

Identyfikatory

DOI

10.3233/FI-222165

• Języki publikacji: EN

Abstrakty

EN

The Kn¨odel graph W∆,n is a ∆-regular bipartite graph on n > 2∆ vertices where n is an even integer. In this paper We obtain some results about the distances of two vertices in the Kndel graphs and by them, we prove that diam(W∆,n) = 1 + d n−2 2∆−2 e, where ∆ > 2 and n > (2∆ − 5)(2∆ − 2) + 4.

Słowa kluczowe

EN

Knödel Graph; distance; diameter

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 190, nr 1
• Strony: 47--62
• Opis fizyczny: Bibliogr. 22 poz. rys., tab.

Twórcy

autor

Musawi Seyed Reza

• Faculty of Mathematical Sciences Shahrood University of Technology P.O. Box 36199-95161, Shahrood, Iran

autor

Nazari Esmaeil

• Department of Mathematics Tafresh University Tafresh, Iran

Bibliografia

• [1] Altay SC, Harutyunyan HA. New Properties for Broadcasting in KG2k . C3S2E, 2014:8. doi:10.1145/2641483.2641532.
• [2] Balakrishnan R. Some properties of the Knӧdel graphs Wk,2k . Australasian Journal of Combinatorics, 2019. 74 (1):17–32. ISSN: 1034-4942.
• [3] Bermond JC, Harutyunyan HA, Liestman AL and Perennes S. A note on the dimensionality of modified Knӧdel graphs. IJFCS: Int. J. Foundations Comput. Sci., 1997. 8 (2): 109–116.
• [4] Bondy JA, Murty USR. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008. ISBN-10:1846289696, ISBN-13: 9781846289699.
• [5] Fertin G, Raspaud A. A survey on Knӧdel graphs. Discrete Applied Mathematics, 2004. 137: 173–195. doi:10.1016/S0166-218X(03)00260-9.
• [6] Fertin G, Raspaud A, Schroder H, Sykora O, Vrto I. Diameter of the Knӧdel graph. Graph-Theoretic Concepts in Computer Science, Springer, 2000. : 149–160. doi:10.1007/3-540-40064-8 15.
• [7] Fraigniaud P, Lazard E. Methods and problems of communication in usual networks. Discrete. Applied Math., 1994. 53(1-3): 79–133.
• [8] Fraigniaud P, Peters JG.. Minimum linear gossip graphs and maximal linear (∆, k)-gossip graphs. Networks, 2001. 38: 150–162.
• [9] Grigoryan H, Harutyunyan HA. The shortest path problem in the Knӧdel graph. J. Discrete Algorithms, 2015. 31: 40–47. doi:10.1016/j.jda.2014.11.008.
• [10] Harutyunyan HA, Liestman AL. Upper bounds on the broadcast function using minimum dominating sets. Discrete Math., 2012. 312(20): 2992–2996. doi:10.1016/j.disc.2012.06.016.bibitemhlpr Harutyunyan HA, Liestman AL, Peters J, Richards D. Broadcasting and Gossiping. The Handbook of Graph Theory, J. Gross, Yellen, P. Zhang eds. Chapman and Hall/CRC, 2013 : 1477-1494.
• [11] Harutyunyan HA, Oad GB. Exploring the diameter and broadcast time of general Knӧdel graphs using extensive simulations. C3S2E, 2014 : 25. doi:10.1145/2641483.2641531.
• [12] Hedetniemi S M, Hedetniemi S T, Liestmant L. A Survey of Gossiping and Broadcasting in Communication Networks. Networks, 1988. 18: 319–349. doi:10.1002/net.3230180406.
• [13] Heydemann M-C, Marlin N, Perennes S. Cayley graphs with complete rotations. Technical report, Laboratoire de Recherche en Informatique (Orsay),1997. TR-1155, Submitted for publication.
• [14] Hovnanyan VH. Gossiping Properties of the Modified Knӧdel graphs. Mathematical Problems of Computer Science, 2016. 46: 126–131. ISSN- 2579-2784, ISSN- 2738-2788.
• [15] Hromkovic J, Klasing R, Monien B, Peine R. Dissemination of information in interconnection networks (broadcasting and gossiping). Combinatorial network theory, 1996 : 125–212.
• [16] Knӧdel W. New gossips and telephones. Discrete Mathematics, 1975. 13: 95.
• [17] Mojdeh DA, Musawi SR, Nazari E. Domination Critical Knӧdel Graphs. Iran J Sci Technol Trans Sci., 2019. 43: 2423-2428. doi:10.1007/s40995-019-00710-8.
• [18] Mojdeh DA, Musawi SR, Nazari E. Domination in 4-regular Knӧdel graphs. Open Math., 2018. 16: 816-825. doi:10.1515/math-2018-0072.
• [19] Mojdeh DA, Musawi SR, Nazari E, Jafari Rad N. Total domination in cubic Knӧdel Graphs. Communications in Combinatorics and Optimization, 2021. 6(2): 221-230. doi:10.22049/CCO.2020.26793.1143.
• [20] Oad GB. Diameter and Broadcast Time of the Knӧdel graph. Masters thesis, Concordia University, 2014. ID: 123262219.
• [21] Slater PJ, Cockayne EJ, Hedetniemi ST. Information Dissemination in Trees. Siam J. Comput., 1981. 10(4): 692-701. doi:10.1137/0210052.
• [22] Xueliang F, Xu X, Yuansheng Y, Feng X. On The Domination Number of Knӧdel Graph W (3, n) IJPAM, 2009. 50(4): 553-558. ID: 54603756