Conjectured bounds for the sum of squares of positive eigenvalues of a graph. (English) Zbl 1339.05228

Elphick, Clive; Farber, Miriam; Goldberg, Felix; Wocjan, Pawel

Discrete Math. 339, No. 9, 2215-2223 (2016).

Summary: A well known upper bound for the spectral radius of a graph, due to Y. Hong [Linear Algebra Appl. 108, 135–139 (1988; Zbl 0655.05047); Discrete Math. 123, No. 1–3, 65–74 (1993; Zbl 0788.05067)], is that \(\mu_1^2 \leq 2 m - n + 1\) if \(\delta \geq 1\). It is conjectured that for connected graphs \(n - 1 \leq s^+ \leq 2 m - n + 1\), where \(s^+\) denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, regular, complete \(q\)-partite, hyper-energetic, and barbell graphs. Various searches have found no counter-examples. The paper concludes with a brief discussion of the apparent difficulties of proving the conjecture in general.

MSC:

05C50

Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

adjacency matrix; inertia of a graph; hyper-energetic graphs

Citations:

Zbl 0655.05047; Zbl 0788.05067

References:

[1]	Ando, T.; Lin, M., Proof of a conjectured lower bound on the chromatic number of a graph, Linear Algebra Appl., 485, 480-484 (2015) · Zbl 1322.05054
[2]	Brooks, R., On colouring the nodes of a network, Proc. Cambridge Philos. Soc., 37, 194-197 (1941) · JFM 67.0733.02
[4]	Constantine, G., Lower bounds on the spectra of symmetric matrices with nonnegative entries, Linear Algebra Appl., 65, 171-178 (1985) · Zbl 0584.15009
[5]	Cvetkovic, D. M.; Doob, M.; Sachs, H., Spectra of graphs, (Johann Ambrosius Barth Verlag (1995)), revised and enlarged · Zbl 0824.05046
[6]	Edwards, C.; Elphick, C., Lower bounds for the clique and the chromatic number of a graph, Discrete Appl. Math., 5, 51-64 (1983) · Zbl 0535.05029
[7]	Hong, Y., A bound on the spectral radius of graphs, Linear Algebra Appl., 108, 135-140 (1988) · Zbl 0655.05047
[8]	Hong, Y., Bounds on eigenvalues of graphs, Discrete Math., 123, 65-74 (1993) · Zbl 0788.05067
[10]	Li, J.; Wang, X., Lower bound on the sum of positive eigenvalues of a graph, Acta Appl. Math., 14, 443-446 (1998) · Zbl 0929.05058
[11]	Nikiforov, V., Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comp., 11, 179-189 (2002) · Zbl 1005.05029
[12]	Nikiforov, V., The energy of graphs and matrices, J. Math. Anal. Appl., 326, 1472-1475 (2007) · Zbl 1113.15016
[13]	Smith, J. H., Some properties of the spectrum of a graph, (Combinat. Structures and their appl. (1970), Gordon and Breach: Gordon and Breach New York), 403-406 · Zbl 0249.05136
[14]	Torgasev, A., On graphs with a fixed number of negative eigenvalues, Discrete Math., 57, 311-317 (1985) · Zbl 0585.05023
[15]	Torgasev, A., Graphs with exactly two negative eigenvalues, Math. Nachr., 122, 135-140 (1985) · Zbl 0584.05048
[16]	Wocjan, P.; Elphick, C., New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, Electron. J. Combin., 20, 3, P39 (2013) · Zbl 1295.05112