PIMS- SFU Discrete Math Seminar: Ambat Vijayakumar

The distance matrix of a connected graph $G$ is an $n \times n$ matrix $D(G) = [d_{ij}]$, where $d_ij$ is the distance between the vertices $v_i$ and $v_j$ . The distance spectrum of $G$ is ${\lambda_1, . . . , \lambda_n}$, where $\lambda_i$ are the eigenvalues of $D(G)$. The distance energy of G is defined by $E_D(G) = \sum_{n=1}^b\left|\lambda_i \right|$. The distance matrix, distance eigenvalue, and distance energy of a connected graph have been studied intensively in literature, see [1, 7, 8, 9, 12]. We discuss a new problem of how the distance energy changes when an edge is deleted. Similar problem for adjacency energy of a graph was studied by Day and So in [3, 4]. It turns out that the results for distance energy change and adjacency energy change are quite different. From an observation in [12], it follows that, for any connected graph with a unique positive eigenvalue, the deletion of any edge increases the distance energy provided that the resulting graph is still connected. We prove that the distance energy of a complete bipartite graph is always increased when an edge is deleted even though it has two positive distance eigenvalues. Also, we give a set of examples of connected graph whose distance energy decreases when a specific edge is deleted. This is a joint work with G.Indulal and A. Varghese.

References

[1] M. Aouchiche and P. Hansen, Distance spectra of graphs: a survey, Linear Algebra and its Applications 458 (2014) 301–386.

[2] R. Bapat, S. Kirkland and M. Neumann, On distance matrices and Laplacians, Linear Algebra and its Applications 401 (2005) 193–209. 1

[3] J. Day and W. So, Singular value inequality and graph energy change, Electron. J. Linear Algebra 16 (2007) 291–299.

[4] J. Day and W. So, Graph energy change due to edge deletion, Linear Algebra and its Applications 428 (2008) 2070–2078.

[5] B. Durgi, P. Hampiholi, S. Mekkalike, Distance spectra and distance energy of some cluster graphs, Mathematica Aeterna 4 (2014) 817 – 825.

[6] R. Horn and C. Johnson, Matrix Analysis, Cambridge University press, 1985.

[7] A. Ilic, Distance spectra and distance energy of integral circulant graphs, Linear Algebra and its Applications 433 (2010) 1005–1014.

[8] G. Indulal, Distance spectrum of graph compositions, Ars Mathematica Contemporanea 2 (2009) 93–100.

[9] G. Indulal, I. Gutman and A. Vijayakumar, On distance energy of graphs, MATCH Commun. Math. Comput. Chem. 60 (2008) 461–472.

[10] W. So, A shorter proof of the distance energy of complete multipartite graphs, Special Matrices 5 (2017) 61–63.

[11] D. Stevanovic and G. Indulal, The distance spectrum and energy of the composition of regular graphs, Appl. Math. Lett. 22 (2009) 1136–1140.

[12] B. Zhou and A. Ilic, On distance spectral radius and distance energy of graphs, MATCH Commun. Math. Comput. Chem. 64 (2010) 261–280.

[13] A. Varghese, W. So, A. Vijayakumar, Distance energy change of Complete-bipartite graph due to edge deletion, Linear Algebra and Applications 553 (2018) 211–222.