PDF
Discussiones Mathematicae Graph Theory 29(1) (2009)
15-37
DOI: https://doi.org/10.7151/dmgt.1430
VARIABLE NEIGHBORHOOD SEARCH FOR EXTREMAL GRAPHS. 17. FURTHER CONJECTURES AND RESULTS ABOUT THE INDEX
|
Mustapha Aouchiche
HEC Montréal |
Pierre Hansen
GERAD and HEC Montréal |
Dragan Stevanović
PINT, University of Primorska, Slovenia |
Abstract
The AutoGraphiX 2 system is used to compare the index of a connected graph G with a number of other graph theoretical invariants, i.e., chromatic number, maximum, minimum and average degree, diameter, radius, average distance, independence and domination numbers. In each case, best possible lower and upper bounds, in terms of the order of G, are sought for sums, differences, ratios and products of the index and another invariant. There are 72 cases altogether: in 7 cases known results were reproduced, in 32 cases immediate results were obtained and automatically proved by the system, conjectures were obtained in 27 cases, of which 12 were proved (in 3 theorems and 9 propositions), 9 remain open and 6 were refuted. No results could be derived in 7 cases.Keywords: AutoGraphiX, automated conjecture making, index of a graph, spectral radius, graph invariant.
2000 Mathematics Subject Classification: 05C35, 05C50, 05C75.
References
| [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
Close