×

Variable neighborhood search for extremal graphs. III: On the largest eigenvalue of color-constrained trees. (English) Zbl 1003.05058

[For Part I see G. Caporossi and P. Hansen, Discrete Math. 212, 29-44 (2000; Zbl 0947.90130).]
Authors’ abstract: In the set of bicolored trees with given numbers of black and of white vertices we describe those for which the largest eigenvalue is extremal (maximal or minimal). The results are first obtained by the automated system AutoGraphiX, developed in GERAD (Montréal), and verified afterwards by theoretical means.
Reviewer: C.Lai (Zhangzhou)

MSC:

05C35 Extremal problems in graph theory
05C05 Trees
05C15 Coloring of graphs and hypergraphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

bicolored trees

Citations:

Zbl 0947.90130

Software:

AutoGraphiX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brualdi, R. A. and Solheid. 1985.On the spectral radius of connected graphs, Vol. 39, 45–54. Beograd: Institut Mathématique Publications. · Zbl 0603.05028
[2] DOI: 10.1016/S0012-365X(99)00206-X · Zbl 0947.90130 · doi:10.1016/S0012-365X(99)00206-X
[3] Caporossi G., Proceedings of XVIth IJCAI Conference 2 pp 781– (1999)
[4] Caporossi G., Journal of Chemical Information and Computer Sciences 39 pp 984– (1999)
[5] DOI: 10.1080/03081089508818383 · Zbl 0831.05043 · doi:10.1080/03081089508818383
[6] Cvetković, D. Spanning trees in the theory of graph spectra. Proc. Second Math. Conf in Pri[stilde]tina. · Zbl 0942.05015
[7] Cvetković D., Variations on the traveling salesman theme (1996)
[8] Cvetković D., Spectra of Graphs-Theory and Application (1995)
[9] Cvetković, D. and Gutman, I. 1975.On spectral structure of graphs having the maximal eigenvalue not greater than two, Vol. 18, 39–45. Beograd: Institut Mathematique Publications. · Zbl 0307.05132
[10] Cvetković D., Elektrotehn.Fak. Ser. Mat. Fiz. 716 pp 100– (1981)
[11] Cvetković D., Eigenspaces of graphs (1997) · Zbl 0878.05057
[12] Cvetković D., Académie Serbe des Sciences et des Arts Classe des Sciences Mathématiques et Naturelles Bulletin Sciences Mathématiques 107 pp 19– (1994)
[13] Hansen P., Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization pp 433– (1998)
[14] Hoffman A. J., Recent Advances in Graph Theory pp 273– (1975)
[15] Li K., Acta Mathematicae Applicatae Sinica 2 pp 167– (1979)
[16] DOI: 10.1007/BF02018473 · Zbl 0247.05108 · doi:10.1007/BF02018473
[17] Simić, S. 1988.On the largest eigenvalue of unicyclic graphs, Vol. 42, 13–19. Beograd: Institut Mathématique Publications. · Zbl 0641.05040
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.