zbMATH — the first resource for mathematics

Eigenvalue interlacing and weight parameters of graphs. (English) Zbl 0933.05099
Suppose a positive eigenvector belonging to the largest eigenvalue of a graph is normalized in such a way that its smallest coordinate is equal to 1. Assigning coordinates of such a vector to vertices as weights, maximal values of the sum of squares of weights of vertices in independent (and some other interesting) vertex subsets are studied. Some known results (e.g. bounds for the Shannon capacity and the chromatic number) are improved and in some cases extended to hold not only for regular graphs. Interlacing theorems for graph eigenvalues are used in the proofs. Similar results are obtained with the Laplacian matrix of a graph but without introducing vertex weights.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI arXiv
[1] Balbuena, C.; Carmona, A.; Fàbrega, J.; Fiol, M.A., On the connectivity and the conditional diameter of graphs and digraphs, Networks, 28, 97-105, (1996) · Zbl 0865.90047
[2] Bannai, E.; Ito, T., Algebraic combinatorics I: association schemes, () · Zbl 0555.05019
[3] Biggs, N., Some odd graph theory, Annals New York acad. sci., 319, 71-81, (1979), New York
[4] Biggs, N., Algebraic graph theory, (), 1993
[5] Bond, I.; Delorme, C., New large bipartite graphs with given degree and diameter, Ars combin., 25C, 123-132, (1988) · Zbl 0649.05043
[6] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer Cambridge · Zbl 0747.05073
[7] F.R.K. Chung, C. Delorme, P. Solé k-Diameter and spectral multiplicity, submitted.
[8] Chung, F.R.K.; Grigor’yan, A.; Yau, S.-T., Upper bounds for eigenvalues for the discrete and continuous Laplace operators, Adv. math., 117, 165-178, (1996) · Zbl 0844.53029
[9] Courant, R.; Hilbert, D., ()
[10] van Dam, E.R., Graphs with few eigenvalues, () · Zbl 1122.05063
[11] van Dam, E.R., Bounds on special subsets in graphs, eigenvalues and association schemes, J. algebraic combin., 7, 3, 321-332, (1998) · Zbl 0974.05052
[12] van Dam, E.R.; Haemers, W.H., Eigenvalues and the diameter of graphs, Linear and multilinear algebra, 39, 33-44, (1995) · Zbl 0831.05046
[13] Delorme, C.; Tillich, J.P., Eigenvalues, eigenspaces and distances to subsets, Discrete math., 165-166, 1-3, 161-184, (1997) · Zbl 0881.05087
[14] Fiol, M.A., Weight odd parameters and spectra of graphs, (), 401-410, Wiley, New York, 1998
[15] Fiol, M.A., An eigenvalue characterization of antipodal distance-regular graphs, Electron. J. combin., 4, 1, R30, (1997) · Zbl 0885.05082
[16] Fiol, M.A.; Garriga, E., The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs, Discrete appl. math., 87, 1-3, 77-97, (1998) · Zbl 0914.05050
[17] M.A. Fiol, E. Garriga, Pseudo-distance-regularity around a set, orthogonal polynomials, and completely regular codes, submitted. · Zbl 0996.05091
[18] Fiol, M.A.; Garriga, E.; Yebra, J.L.A., On a class of polynomials and its relation with the spectra and diameters of graphs, J. combin. theory ser. B, 67, 48-61, (1996) · Zbl 0857.05101
[19] M.A. Fiol, E. Garriga, J.L.A. Yebra, Boundary graphs: The limit case of a spectral property, submitted. · Zbl 0965.05068
[20] Fiol, M.A.; Garriga, E.; Yebra, J.L.A., The alternating polynomials and their relation with the spectra and conditional diameters of graphs, Discrete math., 167-168, 1-3, 297-307, (1997) · Zbl 0877.05017
[21] Garriga, E., Contribució a la teoria espectral de grafs, ()
[22] Godsil, C.D., Algebraic combinatorics, (1993), Chapman and Hall Barcelona · Zbl 0814.05075
[23] Godsil, C.D.; McKay, B.D., Feasibility conditions for the existence of walk-regular graphs, Linear algebra appl., 30, 51-61, (1980) · Zbl 0452.05045
[24] Haemers, W.H., Eigenvalue methods, (), 15-38
[25] Haemers, W.H., Eigenvalue techniques in design and graph theory, () · Zbl 0429.05013
[26] Haemers, W.H., Interlacing eigenvalues and graphs, Linear algebra appl., 226-228, 593-616, (1995) · Zbl 0831.05044
[27] Hoffman, A.J., On eigenvalues and coloring of graphs, (), 79-91
[28] Kahale, N., Isoperimetric inequalities and eigenvalues, SIAM J. discrete math., 10, 1, 30-40, (1997) · Zbl 0917.05039
[29] Knuth, D.K., The sandwich theorem, Electron. J. combin., 1, Al, (1994)
[30] Lovász, L., On the Shannon capacity of a graph, IEEE trans. inform. theory, IT-25, 1, 1-7, (1979) · Zbl 0395.94021
[31] Lovász, L., Combinatorial problems and exercises, (1979), North-Holland New York · Zbl 0439.05001
[32] McKay, B.D., Backtrack programming and the graph isomorphism problem, ()
[33] Mohar, B., The Laplacian spectrum of graphs, (), 871-898 · Zbl 0840.05059
[34] Rodriguez, J.A., Cotas de diversos parámetros de un grafo a partir de los autovalores de su matriz laplaciana, ()
[35] Shannon, C.E., The zero-error capacity of a noisy channel, IRE trans. inform. theory, IT-2, 3, 8-19, (1956)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.