Graphe symétrique

En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u₁—v₁ et u₂—v₂ de G, il existe un automorphisme de graphe :

f:V\rightarrow V

tel que

f(u_{1})=u_{2}

et

f(v_{1})=v_{2}

^[1].

En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés^[2]. Un tel graphe est parfois appelé 1-arc-transitif^[2].

Par définition, un graphe symétrique sans sommet isolé est sommet-transitif^[1] et arête-transitif. La distinction entre arête-transitif et arc-transitif est subtile^[3]: « Arête-transitif » signifie que pour toute paire d'arêtes $u_{1}{-}u_{2}$ et $v_{1}{-}v_{2}$ , il existe un automorphisme $f$ qui envoie l'une sur l'autre, donc tel que $f(u_{1}){-}f(u_{2})=v_{1}{-}v_{2}$ , alors que « arc-transitif » demande qu'en plus $f(u_{1})=v_{1},f(u_{2})=v_{2}$ et que, pour un autre automorphisme $f'$ , on ait $f'(u_{1})=v_{2},f'(u_{2})=v_{1}$ . Si un graphe est arête-transitif sans être 1-transitif, alors toute arête peut être envoyée sur toute autre, mais seulement d'une seule parmi les deux façons possibles.

Le terme « symétrique » est d'ailleurs parfois employé pour désigner un graphe qui soit simplement arête-transitif et sommet-transitif ; cette utilisation du terme est ambiguë, car il existe des graphes qui sont arête-transitifs et sommet-transitifs sans être arc-transitifs^[4]. Ces graphes sont rares : le plus petit exemple est le graphe de Doyle^[5].

Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif^[6].

Les graphes cubiques symétriques

Familles de graphes définies par leurs automorphismes
distance-transitif	→	distance-régulier	←	fortement régulier
↓
symétrique (arc-transitif)	←	t-transitif, $(t \geq 2)$		symétrique gauche (en)
↓
_{(si connexe)} sommet-transitif et arête-transitif	→	régulier et arête-transitif	→	arête-transitif
↓		↓		↓
sommet-transitif	→	régulier	→	_{(si biparti)} birégulier
↑
graphe de Cayley	←	zéro-symétrique		asymétrique

Un graphe cubique est un graphe régulier dont tous les sommets sont de degré 3. Les graphes cubiques symétriques sont les premiers graphes réguliers symétriques intéressants, le cas régulier de degré 2 étant trivial et se résumant aux graphes cycles.

Les graphes cubiques symétriques sont catalogués par Ronald M. Foster à partir de 1934^[7]. En 1988 un livre écrit par Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson et Z. Star est publié contenant une liste, alors jugée exhaustive de tous les graphes cubiques symétriques jusqu'à l'ordre 512^[8]. Quelques spécimens d'ordre inférieur ou égal à 512 manquent en fait à la liste (les graphes F480B, F432E, F448C, F480C, F480D, F486D, F512D, F512E, F512F, F512G). En 2002, Marston Conder complète la liste et l'étend jusqu'à l'ordre 768^[9], puis jusqu'à l'ordre 2048 en 2006 et jusqu'à l'ordre 10000 en 2011^[10]^,^[11].

Les premiers graphes cubiques symétriques (en nombres de sommets) sont regroupés dans la table suivante :

Ordre	Graphe
4	Le graphe tétraédrique (le graphe complet K₄)
6	Le graphe biparti complet K_3,3
8	Le graphe hexaédrique
10	Le graphe de Petersen
14	Le graphe de Heawood
16	Le graphe de Möbius-Kantor
18	Le graphe de Pappus
20	Le graphe de Desargues
20	Le graphe dodécaédrique

En 2008, une version étendue aux graphes réguliers de degrés 4 et 5 mais non exhaustive du Foster Census est établie par Alain Bretto et Luc Gillibert^[12].

Références

↑ ^{a et b} (en) Biggs, Norman, Algebraic Graph Theory, Cambridge, Cambridge University Press, 1993, 2^e éd., poche (ISBN 978-0-521-45897-9, LCCN 94170202), p. 118
↑ ^{a et b} (en) Godsil, Chris, and Royle, Gordon, Algebraic Graph Theory, New York, Springer, 2001, poche (ISBN 978-0-387-95220-8, LCCN 00053776), p. 59
↑ Arc-Transitive Graph sur MathWorld.
↑ (en) Izak Z. Bouwer, "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231-237, 1970.
↑ Peter G. Doyle, « A 27-vertex graph that is vertex-transitive and edge-transitive but not 1-transitive », octobre 1998 (consulté le 30 décembre 2017).
↑ (en) László Babai, chap. 27 « Automorphism groups, isomorphism, reconstruction », dans R. Graham, M. Groetschel et L. Lovasz (éditeurs), Handbook of Combinatorics, Elsevier, 1996 (lire en ligne)
↑ (en) Gordon Royle, Marston Conder, Brendan McKay and Peter Dobscanyi, Cubic symmetric graphs (The Foster Census)
↑ (en) The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs, by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) (ISBN 0919611192)
↑ Marston Conder et Peter Dobcsányi, « Trivalent symmetric graphs on up to 768 vertices », J. Combin. Math. Combin. Comput., vol. 40,‎ 2002, p. 41-63 (MR 1887966, lire en ligne)
↑ (en) Marston Conder, Trivalent (cubic) symmetric graphs on up to 2048 vertices
↑ (en) Marston Conder, Trivalent (cubic) symmetric graphs on up to 10000 vertices
↑ (en) Alain Bretto and Luc Gillibert."G-Graphs: an Efficient Tool for Constructing Symmetric and Semi-Symmetric Graphs". Discrete Applied Mathematics 156 (14) : 2719-2739 (2008).

Article lié

Lexique de la théorie des graphes — définition de « arc-transitif »

Lien externe

(en) Eric W. Weisstein, « Arc-Transitive Graph », sur MathWorld

Portail des mathématiques

[biggs-1] {a et b} (en) Biggs, Norman, Algebraic Graph Theory, Cambridge, Cambridge University Press, 1993, 2^e éd., poche (ISBN 978-0-521-45897-9, LCCN 94170202), p. 118

[godsil-2] {a et b} (en) Godsil, Chris, and Royle, Gordon, Algebraic Graph Theory, New York, Springer, 2001, poche (ISBN 978-0-387-95220-8, LCCN 00053776), p. 59

[3] Arc-Transitive Graph sur MathWorld.

[4] (en) Izak Z. Bouwer, "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231-237, 1970.

[5] Peter G. Doyle, « A 27-vertex graph that is vertex-transitive and edge-transitive but not 1-transitive », octobre 1998 (consulté le 30 décembre 2017).

[babai-6] (en) László Babai, chap. 27 « Automorphism groups, isomorphism, reconstruction », dans R. Graham, M. Groetschel et L. Lovasz (éditeurs), Handbook of Combinatorics, Elsevier, 1996 (lire en ligne)

[7] (en) Gordon Royle, Marston Conder, Brendan McKay and Peter Dobscanyi, Cubic symmetric graphs (The Foster Census)

[8] (en) The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs, by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) (ISBN 0919611192)

[9] Marston Conder et Peter Dobcsányi, « Trivalent symmetric graphs on up to 768 vertices », J. Combin. Math. Combin. Comput., vol. 40,‎ 2002, p. 41-63 (MR 1887966, lire en ligne)

[10] (en) Marston Conder, Trivalent (cubic) symmetric graphs on up to 2048 vertices

[11] (en) Marston Conder, Trivalent (cubic) symmetric graphs on up to 10000 vertices

[12] (en) Alain Bretto and Luc Gillibert."G-Graphs: an Efficient Tool for Constructing Symmetric and Semi-Symmetric Graphs". Discrete Applied Mathematics 156 (14) : 2719-2739 (2008).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]