Recherche à voisinage variable de graphes extrémaux 13. A propos de la maille

Mustapha Aouchiche; Pierre Hansen

RAIRO - Operations Research - Recherche Opérationnelle (2005)

  • Volume: 39, Issue: 4, page 275-293
  • ISSN: 0399-0559

Abstract

top
The AutoGraphiX system (AGX1 et AGX2) allows, among other functions, automated generation of conjectures in graph theory and, in its most recent version, automated proof of simple conjectures. To illustrate these functions and the type of results obtained, we study systematically in this paper, conjectures of the form b ̲ n ≤ g ⊕ i ≤ b ¯ n where g denotes the girth (or length of the smallest cycle) of a graph G = ( V , E ) , i another invariant among independence number, radius,iameter, minimum, average or maximum degree, b ̲ n and b ¯ n best possible functions of the order n of G , and ⊕ denotes one of the four operations + , - , × , / . 48 such conjectures are obtained: the easiest ones are proved automatically and the others by hand. Moreover 12 open and unstudied conjectures are submitted to the readers.

How to cite

top

Aouchiche, Mustapha, and Hansen, Pierre. "Recherche à voisinage variable de graphes extrémaux 13. A propos de la maille." RAIRO - Operations Research - Recherche Opérationnelle 39.4 (2005): 275-293. <http://eudml.org/doc/245300>.

@article{Aouchiche2005,
abstract = {Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d’autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d’illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues par ce système et de la forme $\underline\{b\}_\{n\} \, \le \, g \, \oplus \, i \, \le \, \overline\{b\}_\{n\}$ où $g $ désigne la maille (ou longueur du plus petit cycle) du graphe $G=(V, E)$, $i $ un autre invariant choisi parmi le nombre de stabilité, le rayon, le diamètre, le degré minimum, moyen ou maximum, $\underline\{b\}_\{n\} $ et $ \overline\{b\}_\{n\} $ des fonctions de l’ordre $ n = |V|$ de $G$ les meilleures possibles, enfin $ \oplus $ correspond à une des opérations $ +, -, \times , /$. 48 telles conjectures sont obtenues : les plus simples sont démontrées automatiquement et les autres à la main. De plus 12 autres conjectures ouvertes et non encore étudiées sont soumises aux lecteurs.},
author = {Aouchiche, Mustapha, Hansen, Pierre},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {graphe; invariant; conjecture; AGX; maille},
language = {fre},
number = {4},
pages = {275-293},
publisher = {EDP-Sciences},
title = {Recherche à voisinage variable de graphes extrémaux 13. A propos de la maille},
url = {http://eudml.org/doc/245300},
volume = {39},
year = {2005},
}

TY - JOUR
AU - Aouchiche, Mustapha
AU - Hansen, Pierre
TI - Recherche à voisinage variable de graphes extrémaux 13. A propos de la maille
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 4
SP - 275
EP - 293
AB - Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d’autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d’illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues par ce système et de la forme $\underline{b}_{n} \, \le \, g \, \oplus \, i \, \le \, \overline{b}_{n}$ où $g $ désigne la maille (ou longueur du plus petit cycle) du graphe $G=(V, E)$, $i $ un autre invariant choisi parmi le nombre de stabilité, le rayon, le diamètre, le degré minimum, moyen ou maximum, $\underline{b}_{n} $ et $ \overline{b}_{n} $ des fonctions de l’ordre $ n = |V|$ de $G$ les meilleures possibles, enfin $ \oplus $ correspond à une des opérations $ +, -, \times , /$. 48 telles conjectures sont obtenues : les plus simples sont démontrées automatiquement et les autres à la main. De plus 12 autres conjectures ouvertes et non encore étudiées sont soumises aux lecteurs.
LA - fre
KW - graphe; invariant; conjecture; AGX; maille
UR - http://eudml.org/doc/245300
ER -

References

top
  1. [1] 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. Global Optimization: From Theory to Implementation, edited by L. Liberti and N. Maculan, Springer (2005). Zbl1100.90052
  2. [2] M. Aouchiche, G. Caporossi and P. Hansen, Automated Comparison of Graph Invariants. Les Cahiers du GERAD, G–2005–40, rapport technique, HEC Montréal (2005) 21 pages. Zbl1274.05235
  3. [3] S. Belhaiza, N.M.M. de Abreu, P. Hansen and C.S. Oliveira, Variable Neighborhood Search for Extremal Graphs 11. Bounds on Algebraic Connectivity, edited by D. Avis, A. Hertz and O. Marcotte, Graph Theory and Combinatorial Optimization, Dordrecht, Kluwer (2005) 1–16. Zbl1096.05027
  4. [4] R. C. Brigham and R. D. Dutton, A Compilation of Relations between Graph Invariants. Networks 21 (1991) 421–455. Zbl0743.05057
  5. [5] G. Caporossi, D. Cvetkovic, I. Gutman and P. Hansen, Variable Neighborhood Search for Extremal Graphs. 2. Finding Graphs with Extremal Energy. J. Chem. Inform. Comput. Sci. 39 (1999) 984–996. 
  6. [6] G. Caporossi, I. Gutman and P. Hansen, Variable Neighborhood Search for Extremal Graphs. 4. Chemical Trees with Extremal Connectivity Index. Comput. Chem. 23 (1999) 469–477. 
  7. [7] G. Caporossi and P. Hansen, Variable Neighborhood Search for Extremal Graphs. I. The AutoGraphiX System. Discrete Math. 212 (2000) 29–44. 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. Zbl1031.05068
  9. [9] F.R.K. Chung, The Average Distance and the Independence Number. J. Graph Theory 12 (1988) 229–235. Zbl0644.05029
  10. [10] D. Cvetković, S. Simić, G. Caporossi and P. Hansen, Variable Neighborhood Search for Extremal Graphs. III. On the Largest Eigenvalue of Color-Constrained Trees. Linear Multilinear Algebra 49 (2001) 143–160. Zbl1003.05058
  11. [11] D. Cvetković and S. Simić, Graph Theoretical Results Obtained by the Support of the Expert System “GRAPH” - an Extended Survey. In [13]. Zbl1108.05061
  12. [12] S. Fajtlowicz, On Conjectures of Graffiti. Discrete Math. 72 (1988) 113–118. Zbl0711.68081
  13. [13] Graphs and Discovery. DIMACS Series in Discrete Math. and Theoretical Computer Science, edited by S. Fajtlowicz, P. Fowler, P. Hansen, M. Janowitz and F. Roberts, Providence, AMS (2005). Zbl1087.05001MR2193475
  14. [14] I. Gutman, P. Hansen and H. Mélot, Variable Neighborhood Search for Extremal Graphs. 10. Comparison of Irregularity Indices for Chemical Trees. J. Chem. Inform. Comput. Sci. (2005, to appear). Zbl1274.05241MR2143222
  15. [15] P. Hansen, Computers in Graph Theory. Graph Theory Notes of New York 43 (2002) 20–34. 
  16. [16] P. Hansen, How Far Is, Should and Could Be Conjecture-Making in Graph Theory an Automated Process ? In [13]. Zbl1097.68588
  17. [17] P. Hansen and H. Mélot, Variable Neighborhood Search for Extremal Graphs. 6. Analyzing Bounds for the Connectivity Index. J. Chem. Inform. Comput. Sci. 43 (2003) 1–14. 
  18. [18] P. Hansen and H. Mélot, Variable Neighborhood Search for Extremal Graphs. 9. Bounding the Irregularity of a Graph. In [13]. Zbl1095.05019
  19. [19] P. Hansen and N. Mladenović, Variable Neighborhood Search: Principles and Applications. Eur. J. Oper. Res. 130 (2001) 449–467. Zbl0981.90063
  20. [20] N. Mladenović and P. Hansen, Variable Neighborhood Search. Comput. Oper. Res. 24 (1997) 1097–1100. Zbl0889.90119
  21. [21] E.A. Nordhaus and J.W. Gaddum, On Complementary Graphs. Amer. Math. Monthly 63 (1956) 175–177. Zbl0070.18503
  22. [22] B.A. Smith, Private communication (2004). 
  23. [23] P. Turán, Eine Extremalaufgabe aus der Graphentheorie. (Hungarian) Mat. Fiz. Lapok 48 (1941) 436–452. Zbl0026.26903
  24. [24] Written on the wall. Electronic file available from http://math.uh.edu/~clarson/ (1999). 

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.