Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index

Mustapha Aouchiche ; Pierre Hansen ; Dragan Stevanović

Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 15-37 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2009-01-01

Zbl 1229.05128

EUDML-ID : urn:eudml:doc:270619

Bibliographie

[000] [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/.

[001] [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. | Zbl 1100.90052

[002] [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. | Zbl 1274.05235

[003] [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. | Zbl 1160.90494

[004] [5] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973).

[005] [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. | Zbl 0579.05059

[006] [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. | Zbl 0947.90130

[007] [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. | Zbl 1031.05068

[008] [9] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs-Theory and Applications, 3rd edition (Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995).

[009] [10] E. DeLaVina, Some history of the development of graffiti, in [11], pp. 81-118. | Zbl 1096.05049

[010] [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). | Zbl 1087.05001

[011] [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. | Zbl 1110.05060

[012] [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. | Zbl 1109.05069

[013] [14] P. Hansen, Computers in graph theory, Graph Theory Notes of New York 43 (2002) 20-34.

[014] [15] P. Hansen, How far is, should and could be conjecture-making in graph theory an automated process? in [11], pp. 189-230. | Zbl 1097.68588

[015] [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. | Zbl 1102.68093

[016] [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. | Zbl 1203.05077

[017] [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).

[018] [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. | Zbl 0655.05047

[019] [20] Y. Hong, Bounds of eigenvalues of graphs, Discrete Math. 123 (1993) 65-74, doi: 10.1016/0012-365X(93)90007-G. | Zbl 0788.05067

[020] [21] L. Lovász and J. Pelikán, On the eigenvalues of trees, Periodica Math. Hung. 3 (1973) 175-182, doi: 10.1007/BF02018473. | Zbl 0247.05108

[021] [22] N. Mladenović and P. Hansen, Variable neighborhood search, Comput. Oper. Res. 24 (1997) 1097-1100, doi: 10.1016/S0305-0548(97)00031-2. | Zbl 0889.90119

[022] [23] O. Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ. 38 (1962).

[023] [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. | Zbl 0666.05043

[024] [25] L. Soltés, Transmission in graphs: a bound and vertex removing, Math. Slovaca 41 (1991) 11-16. | Zbl 0765.05097

[025] [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. | Zbl 0617.05045

[026] [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. | Zbl 0144.45202