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

Abstract

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

How to cite

top

Mustapha 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. [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. [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. [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. [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. [5] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973). 
  6. [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. [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. [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. [9] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs-Theory and Applications, 3rd edition (Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995). 
  10. [10] E. DeLaVina, Some history of the development of graffiti, in [11], pp. 81-118. Zbl1096.05049
  11. [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. [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. [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. [14] P. Hansen, Computers in graph theory, Graph Theory Notes of New York 43 (2002) 20-34. 
  15. [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. [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. [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. [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. [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. [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. [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. [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. [23] O. Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ. 38 (1962). 
  24. [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. [25] L. Soltés, Transmission in graphs: a bound and vertex removing, Math. Slovaca 41 (1991) 11-16. Zbl0765.05097
  26. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.