Discussiones Mathematicae Graph Theory 29(1) (2009)
15-37
doi: 10.7151/dmgt.1430
Mustapha Aouchiche
HEC Montréal |
Pierre Hansen
GERAD and HEC Montréal |
Dragan Stevanović
PINT, University of Primorska, Slovenia |
Keywords: AutoGraphiX, automated conjecture making, index of a graph, spectral radius, graph invariant.
2000 Mathematics Subject Classification: 05C35, 05C50, 05C75.
[1] | M. Aouchiche, Comparaison Automatisée d'Invariants en Théorie des Graphes, PhD Thesis (French), École Polytechnique de Montréal, February 2006, available at "http://www.gerad.ca/∼agx/". |
[2] | M. Aouchiche, J.-M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, L. Hiesse, J. Lacheré and A. Monhait, Variable neighborhood search for extremal graphs, 14. The AutoGraphiX 2 System, in: L. Liberti and N. Maculan (eds), Global Optimization: From Theory to Implementation (Springer, 2006) 281-310. |
[3] | M. Aouchiche, G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs, 20. Automated comparison of graph invariants, MATCH Commun. Math. Comput. Chem. 58 (2007) 365-384. |
[4] | M. Aouchiche, F.K. Bell, D. Cvetković, P. Hansen, P. Rowlinson, S. Simić and D. Stevanović, Variable neighborhood search for extremal graphs, 16. Some conjectures related to the largest eigenvalue of a graph, European J. Oper. Res. 191 (2008) 661-676, doi: 10.1016/j.ejor.2006.12.059. |
[5] | C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973). |
[6] | R.C. Brigham and R.D. Dutton, A compilation of relations between graph invariants, Networks 15 (1985) 73-107, doi: 10.1002/net.3230150108. |
[7] | G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs, I. The AutoGraphiX System, Discrete Math. 212 (2000) 29-44, doi: 10.1016/S0012-365X(99)00206-X. |
[8] | G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs, V. Three ways to automate finding conjectures, Discrete Math. 276 (2004) 81-94, doi: 10.1016/S0012-365X(03)00311-X. |
[9] | D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs-Theory and Applications, 3rd edition (Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995). |
[10] | E. DeLaVina, Some history of the development of graffiti, in [11], pp. 81-118. |
[11] | S. Fajtlowicz, P. Fowler, P. Hansen, M. Janowitz and F. Roberts, Graphs and Discovery, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 69 (AMS, Providence, RI, 2005). |
[12] | L. Feng, Q. Li and X.-D. Zhang, Minimizing the Laplacian eigenvalues for trees with given domination number, Linear Algebra Appl. 419 (2006) 648-655, doi: 10.1016/j.laa.2006.06.008. |
[13] | L. Feng, Q. Li and X.-D. Zhang, Spectral radii of graphs with given chromatic number, Applied Math. Lett. 20 (2007) 158-162, doi: 10.1016/j.aml.2005.11.030. |
[14] | P. Hansen, Computers in graph theory, Graph Theory Notes of New York 43 (2002) 20-34. |
[15] | P. Hansen, How far is, should and could be conjecture-making in graph theory an automated process? in [11], pp. 189-230. |
[16] | P. Hansen, M. Aouchiche, G. Caporossi, H. Mélot and D. Stevanović, What forms do interesting conjectures have in graph theory? in [11], pp. 231-252. |
[17] | P. Hansen and D. Stevanović, On bags and bugs, Electronic Notes in Discrete Math. 19 (2005) 111-116, full version accepted for publication in Discrete Appl. Math, doi: 10.1016/j.endm.2005.05.016. |
[18] | A. Hoffman, On Limit Points of Spectral Radii of non-Negative Symmetric Integral Matrices, in: Graph Theory and Applications (Lecture Notes in Mathematics 303, eds. Y. Alavi, D.R. Lick, A.T. White), (Springer-Verlag, Berlin-Heidelberg-New York, 165-172). |
[19] | Y. Hong, A bound on the spectral radius of graphs, Linear Algebra Appl. 108 (1988) 135-139, doi: 10.1016/0024-3795(88)90183-8. |
[20] | Y. Hong, Bounds of eigenvalues of graphs, Discrete Math. 123 (1993) 65-74, doi: 10.1016/0012-365X(93)90007-G. |
[21] | L. Lovász and J. Pelikán, On the eigenvalues of trees, Periodica Math. Hung. 3 (1973) 175-182, doi: 10.1007/BF02018473. |
[22] | N. Mladenović and P. Hansen, Variable neighborhood search, Comput. Oper. Res. 24 (1997) 1097-1100, doi: 10.1016/S0305-0548(97)00031-2. |
[23] | O. Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ. 38 (1962). |
[24] | P. Rowlinson, On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl. 110 (1988) 43-53, doi: 10.1016/0024-3795(83)90131-3. |
[25] | L. Soltés, Transmission in graphs: a bound and vertex removing, Math. Slovaca 41 (1991) 11-16. |
[26] | R.P. Stanley, A bound on the spectral radius of a graph with e edges, Linear Algebra Appl. 87 (1987) 267-269, doi: 10.1016/0024-3795(87)90172-8. |
[27] | H.S. Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc. 42 (1967) 330-332, doi: 10.1112/jlms/s1-42.1.330. |
Received 23 July 2007
Revised 16 October 2008
Accepted 16 October 2008