Geodesic
Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 1, pp. 15-37.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2009_29_1_a1,
     author = {Aouchiche, Mustapha and Hansen, Pierre and Stevanovi\'c, Dragan},
     title = {Variable neighborhood search for extremal graphs. 17. {Further} conjectures and results about the index},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {15--37},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a1/}
}
TY  - JOUR
AU  - Aouchiche, Mustapha
AU  - Hansen, Pierre
AU  - Stevanović, Dragan
TI  - Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 15
EP  - 37
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a1/
LA  - en
ID  - DMGT_2009_29_1_a1
ER  - 
%0 Journal Article
%A Aouchiche, Mustapha
%A Hansen, Pierre
%A Stevanović, Dragan
%T Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 15-37
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a1/
%G en
%F DMGT_2009_29_1_a1
Aouchiche, Mustapha; Hansen, Pierre; Stevanović, Dragan. Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 1, pp. 15-37. http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a1/

[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.