On Spectra Of Variants Of The Corona Of Two Graphs And Some New Equienergetic Graphs

Adiga, Chandrashekar ; Rakshith, B.R.

Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 127-140.

Résumé

Let G and H be two graphs. The join G ∨ H is the graph obtained by joining every vertex of G with every vertex of H. The corona G ○ H is the graph obtained by taking one copy of G and |V (G)| copies of H and joining the i-th vertex of G to every vertex in the i-th copy of H. The neighborhood corona G★H is the graph obtained by taking one copy of G and |V (G)| copies of H and joining the neighbors of the i-th vertex of G to every vertex in the i-th copy of H. The edge corona G ◇ H is the graph obtained by taking one copy of G and |E(G)| copies of H and joining each terminal vertex of i-th edge of G to every vertex in the i-th copy of H. Let G₁, G₂, G₃ and G₄ be regular graphs with disjoint vertex sets. In this paper we compute the spectrum of (G₁ ∨ G₂) ∪ (G1 ★ G₃), (G₁ ∨ G₂) ∪ (G₂ ★ G₃) ∪ (G₁ ★ G₄), (G₁ ∨ G₂) ∪ (G₁ ○ G₃), (G₁ ∨ G₂) ∪ (G₂ ○ G₃) ∪ (G₁ ○ G₄), (G₁ ∨ G₂) ∪ (G₁ ◇ G₃), (G₁ ∨ G₂) ∪ (G₂ ◇ G₃) ∪ (G₁ ◇ G₄), (G₁ ∨ G₂) ∪ (G₂ ○ G₃) ∪ (G₁ ★ G₃), (G₁ ∨ G₂) ∪ (G₂ ○ G₃) ∪ (G₁ ◇ G₄) and (G₁ ∨ G₂) ∪ (G₂ ★ G₃) ∪ (G₁ ◇ G₄). As an application, we show that there exist some new pairs of equienergetic graphs on n vertices for all n ≥ 11.

Détail

Keywords: spectrum, corona, neighbourhood corona, edge corona, energy of a graph, equienergetic graphs

Bibliographie

[1] C. Adiga, R. Balakrishnan and W. So, The skew energy of a digraph, Linear Algebra Appl. 432 (2010) 1825–1835. doi:10.1016/j.laa.2009.11.034

[2] R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287–295. doi:10.1016/j.laa.2004.02.038

[3] R.B. Bapat, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129–132.

[4] S. Barik, S. Pati and B.K. Sarma, The spectrum of the corona of two graphs, SIAM J. Discrete Math. 21 (2007) 47–56. doi:10.1137/050624029

[5] S.B. Bozkurt, A.D. Gungor and I. Gutman, Note on distance energy of graphs, MATCH. Commun. Math. Comput. Chem. 64 (2010) 129–134.

[6] V. Brankov, D. Stevanović and I. Gutman, Equienergetic chemical trees, J. Serb. Chem. Soc. 69 (2004) 549–553. doi:10.2298/JSC0407549B

[7] S.-Y. Cui and G.-X. Tian, The spectrum and the signless Laplacian spectrum of coronae, Linear Algebra Appl. 437 (2012) 1692–1703. doi:10.1016/j.laa.2012.05.019

[8] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Application (Academic Press, New York, 1980).

[9] W.L. Ferrar, A Text-Book of Determinants, Matrices and Algebraic Forms (Oxford University Press, 1953).

[10] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970) 322–325. doi:10.1007/BF01844162

[11] S. Gong, X. Li, G. Xu, I. Gutman and B. Furtula, Borderenergetic graphs, MATCH Commun. Math. Comput. Chem. 74 (2015) 321–332.

[12] I. Gutman, The energy of a graph, Ber. Math.-Statist. Sekt. Forschungsz. Graz 103 (1978) 1–22.

[13] I. Gutman, The energy of a graph: old and new results, in: Algebraic Combinatorics and Applications, A. Betten, A. Kohnert, R. Laue and A. Wassermann (Ed(s)), (Berlin, Springer, 2000) 196–211.

[14] I. Gutman, Topology and stability of conjugated hydrocarbons. The dependence of total π-electron energy on molecular topology, J. Serb. Chem. Soc. 70 (2005) 441–456. doi:10.2298/JSC0503441G

[15] I. Gutman, D. Kiani, M. Mirzakhah and B. Zhou, On incidence energy of a graph, Linear Algebra Appl. 431 (2009) 1223–1233. doi:10.1016/j.laa.2009.04.019

[16] Y. Hou and W.-C. Shiu, The spectrum of the edge corona of two graphs, Electron. J. Linear Algebra 20 (2010) 586–594. doi:10.13001/1081-3810.1395

[17] G. Indulal, The spectrum of neighborhood corona of graphs, Kragujevac J. Math. 35 (2011) 493–500.

[18] G. Indulal and A. Vijayakumar, On a pair of equienergetic graphs, MATCH. Commun. Math. Comput. Chem. 55 (2006) 83–90.

[19] X. Li, Y. Shi and I. Gutman, Graph Energy (Springer, New York, 2012). doi:10.1007/978-1-4614-4220-2

[20] X. Li, M. Wei and S. Gong, A computer search for the borderenergetic graphs of order 10, MATCH Commun. Math. Comput. Chem. 74 (2015) 333–342.

[21] B. Liu, Y. Huang and Z. You, A survey on the Laplacian-energy-like invariant, MATCH. Commun. Math. Comput. Chem. 66 (2011) 713–730.

[22] J. Liu and B. Liu, On a pair of equienergetic graphs, MATCH. Commun. Math. Comput. Chem. 59 (2008) 275–278.

[23] X. Liu and S. Zhou, Spectra of the neighbourhood corona of two graphs, Linear Multilinear Algebra 62 (2014) 1205–1219. doi:10.1080/03081087.2013.816304

[24] C. McLeman and E. McNicholas, Spectra of coronae, Linear Algebra Appl. 435 (2011) 998–1007. doi:10.1016/j.laa.2011.02.007

[25] H.S. Ramane, I. Gutman, H.B. Walikar and S.B. Halkarni, Equienergetic complement graphs, Kragujevac J. Sci. 27 (2005) 67–74.

[26] H.S. Ramane and H.B. Walikar, Construction of equienergetic graphs, MATCH Commun. Math. Comput. Chem. 57 (2007) 203–210.

[27] D. Stevanović, Energy and NEPS of graphs, Linear Multilinear Algebra 53 (2005) 67–74. doi:10.1080/03081080410001714705

[28] D. Stevanović and I. Stanković, Remarks on hyperenergetic circulant graphs, Linear Algebra Appl. 400 (2005) 345–348. doi:10.1016/j.laa.2005.01.001

[29] L. Xu and Y. Hou, Equienergetic bipartite graphs, MATCH Commun. Math. Comput. Chem. 57 (2007) 363–370.