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

Mustapha Aouchiche; Pierre Hansen; Dragan Stevanović

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 1, page 15-37
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMustapha Aouchiche, Pierre Hansen, and Dragan Stevanović. "Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index." Discussiones Mathematicae Graph Theory 29.1 (2009): 15-37. <http://eudml.org/doc/270619>.

@article{MustaphaAouchiche2009,

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.},

author = {Mustapha Aouchiche, Pierre Hansen, Dragan Stevanović},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {AutoGraphiX; automated conjecture making; index of a graph; spectral radius; graph invariant; AutoGraphiX 2; AGX2},

language = {eng},

number = {1},

pages = {15-37},

title = {Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index},

url = {http://eudml.org/doc/270619},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Mustapha Aouchiche

AU - Pierre Hansen

AU - Dragan Stevanović

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

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 1

SP - 15

EP - 37

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

LA - eng

KW - AutoGraphiX; automated conjecture making; index of a graph; spectral radius; graph invariant; AutoGraphiX 2; AGX2

UR - http://eudml.org/doc/270619

ER -

## References

top- [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. Zbl1100.90052
- [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. Zbl1274.05235
- [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. Zbl1160.90494
- [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. Zbl0579.05059
- [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. Zbl0947.90130
- [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. Zbl1031.05068
- [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. Zbl1096.05049
- [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). Zbl1087.05001
- [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. Zbl1110.05060
- [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. Zbl1109.05069
- [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. Zbl1097.68588
- [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. Zbl1102.68093
- [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. Zbl1203.05077
- [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. Zbl0655.05047
- [20] Y. Hong, Bounds of eigenvalues of graphs, Discrete Math. 123 (1993) 65-74, doi: 10.1016/0012-365X(93)90007-G. Zbl0788.05067
- [21] L. Lovász and J. Pelikán, On the eigenvalues of trees, Periodica Math. Hung. 3 (1973) 175-182, doi: 10.1007/BF02018473. Zbl0247.05108
- [22] N. Mladenović and P. Hansen, Variable neighborhood search, Comput. Oper. Res. 24 (1997) 1097-1100, doi: 10.1016/S0305-0548(97)00031-2. Zbl0889.90119
- [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. Zbl0666.05043
- [25] L. Soltés, Transmission in graphs: a bound and vertex removing, Math. Slovaca 41 (1991) 11-16. Zbl0765.05097
- [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. Zbl0617.05045
- [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. Zbl0144.45202

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.