Previous |  Up |  Next

Article

MSC: 05C50
Full entry | Fulltext not available (moving wall 24 months)      Feedback
Keywords:
distance spectrum; integral graph; distance integral graph; complete multipartite graph
Summary:
A graph is called distance integral (or $D$-integral) if all eigenvalues of its distance matrix are integers. In their study of $D$-integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$-integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_{1},p_{2},p_{3}}$ with $p_{1}<p_{2}<p_{3}$, and $K_{p_{1},p_{2},p_{3},p_{4}}$ with $p_{1}<p_{2}<p_{3}<p_{4}$, as well as the infinite classes of distance integral complete multipartite graphs $K_{a_{1} p_{1},a_{2} p_{2},\ldots ,a_{s} p_{s}}$ with $s=5,6$.
References:
[1] Andreescu, T., Andrica, D., Cucurezeanu, I.: An Introduction to Diophantine Equations. A Problem-Based Approach. Birkhäuser New York (2010). MR 2723590 | Zbl 1226.11001
[2] Aouchiche, M., Hansen, P.: Distance spectra of graphs: a survey. Linear Algebra Appl. 458 (2014), 301-386. MR 3231823 | Zbl 1295.05093
[3] Balińska, K., Cvetković, D., Radosavljević, Z., Simić, S., Stevanović, D.: A survey on integral graphs. Publ. Elektroteh. Fak., Univ. Beogr., Ser. Mat. 13 (2002), 42-65. MR 1992839 | Zbl 1051.05057
[4] Clark, J., Kettle, S. F. A.: Incidence and distance matrices. Inorg. Chim. Acta 14 (1975), 201-205. DOI 10.1016/S0020-1693(00)85743-6
[5] Du, Z., Ilić, A., Feng, L.: Further results on the distance spectral radius of graphs. Linear Multilinear Algebra 61 (2013), 1287-1301. DOI 10.1080/03081087.2012.750654 | MR 3175365 | Zbl 1272.05110
[6] Güngör, A. D., Bozkurt, Ş. B.: On the distance spectral radius and the distance energy of graphs. Linear Multilinear Algebra 59 (2011), 365-370. DOI 10.1080/03081080903503678 | MR 2802519 | Zbl 1223.05174
[7] Harary, F., Schwenk, A. J.: Which graphs have integral spectra?. Graphs Combinatorics, Proc. Capital Conf., Washington, 1973, Lect. Notes Math. 406 Springer, Berlin (1974), 45-51. DOI 10.1007/BFb0066434 | MR 0387124
[8] Ilić, A.: Distance spectra and distance energy of integral circulant graphs. Linear Algebra Appl. 433 (2010), 1005-1014. MR 2658651 | Zbl 1215.05105
[9] Indulal, G., Gutman, I., Vijayakumar, A.: On distance energy of graphs. MATCH Commun. Math. Comput. Chem. 60 (2008), 461-472. MR 2457864 | Zbl 1199.05226
[10] Pokorný, M., Híc, P., Stevanović, D., Milošević, M.: On distance integral graphs. Discrete Math. 338 (2015), 1784-1792. DOI 10.1016/j.disc.2015.03.004 | MR 3351701 | Zbl 1315.05045
[11] Renteln, P.: The distance spectra of Cayley graphs of Coxeter groups. Discrete Math. 311 (2011), 738-755. DOI 10.1016/j.disc.2011.01.021 | MR 2774230 | Zbl 1233.05132
[12] Stevanović, D., Indulal, G.: The distance spectrum and energy of the compositions of regular graphs. Appl. Math. Lett. 22 (2009), 1136-1140. DOI 10.1016/j.aml.2008.11.007 | MR 2523015 | Zbl 1179.05040
[13] Stevanović, D., Milošević, M., Híc, P., Pokorný, M.: Proof of a conjecture on distance energy of complete multipartite graphs. MATCH Commun. Math. Comput. Chem. 70 (2013), 157-162. MR 3136757 | Zbl 1299.05233
[14] Yang, R., Wang, L.: Distance integral complete multipartite graphs with $s=5,6$. (2015), 6 pages Preprint arXiv:1511.04983v1 [math.CO]. MR 3359263
[15] Yang, R., Wang, L.: Distance integral complete $r$-partite graphs. Filomat 29 (2015), 739-749. DOI 10.2298/FIL1504739Y | MR 3359263
[16] Zhou, B., Ilić, A.: On distance spectral radius and distance energy of graphs. MATCH Commun. Math. Comput. Chem. 64 (2010), 261-280. MR 2677587 | Zbl 1265.05437
Partner of
EuDML logo