Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille

Mustapha Aouchiche; Odile Favaron; Pierre Hansen

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 4, page 339-358
  • ISSN: 0399-0559

Abstract

top
Using the AutoGraphiX 2 system (AGX2), we study relations between graph invariants of the form where g denotes the girth of a graph G=(V, E), i another invariant among the average distance l ¯ , the index λ1, the Randić index R and the domination number β, ⊕ denotes one of the four operations +, -, ×, /, b ̲ n and b ¯ n lower and upper bounding functions of the order n of the graph considered which are tight for all n (except possibly very small values due to border effects). The results proved or discussed below were first presented as conjectures in a previous paper published in RAIRO Operations Research [RAIRO Oper. Res. 39 (2005) 275–293].

How to cite

top

Aouchiche, Mustapha, Favaron, Odile, and Hansen, Pierre. "Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille." RAIRO - Operations Research 43.4 (2009): 339-358. <http://eudml.org/doc/250628>.

@article{Aouchiche2009,
abstract = { On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme \[ \underline\{b\}\_\{n\} \, \le \, g \, \oplus \, i \, \le \, \overline\{b\}\_\{n\} \] où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne $\overline\{l\}$, l'index λ1, l'indice de Randić R et le nombre de domination β, $\oplus$ désigne l'une des opérations +, -, ×, /, $\underline\{b\}_\{n\}$ et $\overline\{b\}_\{n\}$ des fonctions de l'ordre n du graphe qui bornent l'expression $g\oplus i$ et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous ont déjà été présentés, sous forme de conjectures, dans un article précédent paru dans RAIRO Recherche Opérationnelle [RAIRO Oper. Res. 39 (2005) 275–293]. },
author = {Aouchiche, Mustapha, Favaron, Odile, Hansen, Pierre},
journal = {RAIRO - Operations Research},
keywords = {Graphe; AGX; maille; distance; Randić; index; domination.},
language = {fre},
month = {10},
number = {4},
pages = {339-358},
publisher = {EDP Sciences},
title = {Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille},
url = {http://eudml.org/doc/250628},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Aouchiche, Mustapha
AU - Favaron, Odile
AU - Hansen, Pierre
TI - Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille
JO - RAIRO - Operations Research
DA - 2009/10//
PB - EDP Sciences
VL - 43
IS - 4
SP - 339
EP - 358
AB - On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme \[ \underline{b}_{n} \, \le \, g \, \oplus \, i \, \le \, \overline{b}_{n} \] où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne $\overline{l}$, l'index λ1, l'indice de Randić R et le nombre de domination β, $\oplus$ désigne l'une des opérations +, -, ×, /, $\underline{b}_{n}$ et $\overline{b}_{n}$ des fonctions de l'ordre n du graphe qui bornent l'expression $g\oplus i$ et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous ont déjà été présentés, sous forme de conjectures, dans un article précédent paru dans RAIRO Recherche Opérationnelle [RAIRO Oper. Res. 39 (2005) 275–293].
LA - fre
KW - Graphe; AGX; maille; distance; Randić; index; domination.
UR - http://eudml.org/doc/250628
ER -

References

top
  1. M. Aouchiche, Comparaison automatisée d'invariants en théorie des graphes. Ph.D. Thesis, École Polytechnique de Montréal, February (2006). Disponible sur www.gerad.ca/ agx.  
  2. 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.  
  3. 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 Global Optimization: From theory to implementation, edited by L. Liberti and N. Maculan, Springer (2006) 281–310.  
  4. M. Aouchiche and P. Hansen, Recherche à voisinage variable de graphes extrémaux. XIII. À propos de la maille. (French) RAIRO-Oper. Res. 39 (2005) 275–293.  
  5. M. Aouchiche, P. Hansen and M. Zheng, Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the Randić index. MATCH Commun. Math. Comput. Chem. 58 (2007) 83–102.  
  6. B. Bollobás and P. Erdös, Graphs of extremal weights. Ars Combin. 50 (1998) 225–233.  
  7. J.A. Bondy and F.Y. Halberstam, Parity theorems for paths and cycles in graphs. J. Graph Theory10 (1986) 107–115.  
  8. G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. I. The AutGraphiX system. Disc. Math. 212 (2000) 29–44.  
  9. D. Cvetković, M. Doob and H. Sachs, Spectra of graphs – Theory and application. Academic Press, New York (1982).  
  10. D. Cvetković and P. Rowlinson, Spectra of unicyclic graphs. Graphs and combinatorics3 (1987) 7–23.  
  11. C. Delorme, O. Favaron and D. Rautenbach, On the Randić index. Discrete Math. 257 (2002) 29–38.  
  12. F.M. Dong and K.M. Koh, The Sizes of Graph with Small Girth. Bull. Inst. Combin. Appl. 18 (1996) 33–44.  
  13. R.D. Dutton and R.C. Brigham, Edges in Graphs with Large Girth. Graphs Combin. 7 (1991) 315–321.  
  14. A.J. Hoffman, On Limit Points of Spectral Radii of Non-Negative Symmetric Integral Matrices, in Graph Theory and Applications. Lect. Notes Math. 303, edited by Y. Alavi, D.R. Lick, A.T. White, Springer-Verlag, Berlin (1972) 165–172.  
  15. Q. Li, and K.Q. Feng, On the largest eigenvalue of a graph. Acta Math. Appl. Sinica2 (1979) 167–175.  
  16. G. Liu, Y. Zhu and J. Cai, On the Randić index of unicyclic graphs with girth g. MATCH Commun. Math. Comput. Chem. 58 (2007) 127–138.  
  17. P. Turán, An extremal problem in graph theory. Mat. Fiz. Lapok48 (1941) 436–452.  

NotesEmbed ?

top

You must be logged in to post comments.