Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille
RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 4, pp. 339-358.

On étudie à l’aide du système AutoGraphiX 2 (AGX 2) des relations de la forme

b ̲ n gib ¯ n
g désigne la maille d’un graphe G=(V,E), i un autre invariant parmi la distance moyenne l ¯, l’index λ 1 , l’indice de Randić R et le nombre de domination β, désigne l’une des opérations +,-,×,/, b ̲ n et b ¯ n des fonctions de l’ordre n du graphe qui bornent l’expression gi 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].

Using the AutoGraphiX 2 system (AGX2), we study relations between graph invariants of the form

b ̲ n gib ¯ n
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].

DOI : 10.1051/ro/2009022
Classification : 05C35, 05C12
Keywords: graph, AGX, girth, distance, Randić, index, domination
Mots clés : graphe, AGX, maille, distance, Randić, index, domination
@article{RO_2009__43_4_339_0,
     author = {Aouchiche, Mustapha and Favaron, Odile and Hansen, Pierre},
     title = {Recherche \`a voisinage variable de graphes extr\'emaux 26. {Nouveaux} r\'esultats sur la maille},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {339--358},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {4},
     year = {2009},
     doi = {10.1051/ro/2009022},
     mrnumber = {2573991},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2009022/}
}
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 - Recherche Opérationnelle
PY  - 2009
SP  - 339
EP  - 358
VL  - 43
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2009022/
DO  - 10.1051/ro/2009022
LA  - en
ID  - RO_2009__43_4_339_0
ER  - 
%0 Journal Article
%A Aouchiche, Mustapha
%A Favaron, Odile
%A Hansen, Pierre
%T Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 339-358
%V 43
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2009022/
%R 10.1051/ro/2009022
%G en
%F RO_2009__43_4_339_0
Aouchiche, Mustapha; Favaron, Odile; Hansen, Pierre. Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 4, pp. 339-358. doi : 10.1051/ro/2009022. http://archive.numdam.org/articles/10.1051/ro/2009022/

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

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

[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. | Numdam | MR | Zbl

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

[6] B. Bollobás and P. Erdös, Graphs of extremal weights. Ars Combin. 50 (1998) 225-233. | MR | Zbl

[7] J.A. Bondy and F.Y. Halberstam, Parity theorems for paths and cycles in graphs. J. Graph Theory 10 (1986) 107-115. | MR | Zbl

[8] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. I. The AutGraphiX system. Disc. Math. 212 (2000) 29-44. | MR | Zbl

[9] D. Cvetković, M. Doob and H. Sachs, Spectra of graphs - Theory and application. Academic Press, New York (1982). | MR

[10] D. Cvetković and P. Rowlinson, Spectra of unicyclic graphs. Graphs and combinatorics 3 (1987) 7-23. | MR | Zbl

[11] C. Delorme, O. Favaron and D. Rautenbach, On the Randić index. Discrete Math. 257 (2002) 29-38. | MR | Zbl

[12] F.M. Dong and K.M. Koh, The Sizes of Graph with Small Girth. Bull. Inst. Combin. Appl. 18 (1996) 33-44. | MR | Zbl

[13] R.D. Dutton and R.C. Brigham, Edges in Graphs with Large Girth. Graphs Combin. 7 (1991) 315-321. | MR | Zbl

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

[15] Q. Li, and K.Q. Feng, On the largest eigenvalue of a graph. Acta Math. Appl. Sinica 2 (1979) 167-175. | MR

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

[17] P. Turán, An extremal problem in graph theory. Mat. Fiz. Lapok 48 (1941) 436-452. | Zbl

Cité par Sources :