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

Aouchiche, Mustapha; Favaron, Odile; Hansen, Pierre

doi:10.1051/ro/2009022

Aouchiche, Mustapha ; Favaron, Odile ; Hansen, Pierre

RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 4, pp. 339-358

Voir la notice de l'article provenant de la source Numdam

Abstract (VO)
Résumé

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

{\underset{̲}{b}}_{n} \leq g \oplus i \leq {\bar{b}}_{n}

where

g

denotes the girth of a graph

G = (V, E)

,

i

another invariant among the average distance

\bar{l}

, the index

λ_{1}

, the Randić index

R

and the domination number

β

,

\oplus

denotes one of the four operations

+, -, \times, /

,

{\underset{̲}{b}}_{n}

and

{\bar{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].

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

{\underset{̲}{b}}_{n} \leq g \oplus i \leq {\bar{b}}_{n}

où

g

désigne la maille d’un graphe

G = (V, E)

,

i

un autre invariant parmi la distance moyenne

\bar{l}

, l’index

λ_{1}

, l’indice de Randić

R

et le nombre de domination

β

,

\oplus

désigne l’une des opérations

+, -, \times, /

,

{\underset{̲}{b}}_{n}

et

{\bar{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].

MR

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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :

Parcourir par

Geodesic

Parcourir par