On bipartite graphs with minimal energy

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

25 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)869-873
Journal / PublicationDiscrete Applied Mathematics
Volume157
Issue number4
Publication statusPublished - 28 Feb 2009

Abstract

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. In a paper [G. Caporossi, D. Cvetkovi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996] Caporossi et al. conjectured that among all connected graphs G with n ≥ 6 vertices and n - 1 ≤ m ≤ 2 (n - 2) edges, the graphs with minimum energy are the star Sn with m - n + 1 additional edges all connected to the same vertices for m ≤ n + ⌊ (n - 7) / 2 ⌋, and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. The conjecture is proved to be true for m = n - 1, 2 (n - 2) in the same paper by Caporossi et al. themselves, and for m = n by Hou in [Y. Hou, Unicyclic graphs with minimal energy, J. Math. Chem. 29 (2001) 163-168]. In this paper, we give a complete solution for the second part of the conjecture on bipartite graphs. Moreover, we determine the graph with the second-minimal energy in all connected bipartite graphs with n vertices and m (n ≤ m ≤ 2 n - 5) edges. © 2008 Elsevier B.V. All rights reserved.

Research Area(s)

  • Bipartite graph, Characteristic polynomial, Eigenvalue, Minimal energy

Citation Format(s)

On bipartite graphs with minimal energy. / Li, Xueliang; Zhang, Jianbin; Wang, Lusheng.
In: Discrete Applied Mathematics, Vol. 157, No. 4, 28.02.2009, p. 869-873.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review