Graphe distance-transitif

Familles de graphes définies par leurs automorphismes
distance-transitif	→	distance-régulier	←	fortement régulier
↓
symétrique (arc-transitif)	←	t-transitif, (t ≥ 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

Graphe de Biggs-Smith, le plus grand graphe cubique distance-transitif.

En théorie des graphes, un graphe non-orienté est distance-transitif si pour tous sommets u, v, x, y tels que u et v d'une part et x et y d'autre part sont à même distance, il existe un automorphisme de graphe envoyant u sur x et v sur y^[1]. Autrement dit, un graphe est distance-transitif si son groupe d'automorphisme agit transitivement sur chacun des ensembles de paires de sommets à même distance^[2].

Propriétés

Tout graphe distance-transitif est distance-régulier^[3]. La réciproque est fausse et le plus petit graphe distance-régulier mais pas distance-transitif est le graphe de Shrikhande^[2].

Tout graphe distance-transitif est symétrique.

Exemples

Les graphes complets, les graphes bipartis complets, les hypercubes sont distance-transitifs^[3].

Graphes cubiques distance-transitifs

Il existe exactement 12 graphes cubiques distance-transitifs^[4] : le graphe tétraédrique, le graphe biparti complet K_3,3, le graphe hexaédrique, le graphe de Petersen, le graphe de Heawood, le graphe de Pappus, le graphe de Desargues, le graphe dodécaédrique, le graphe de Coxeter, le graphe de Tutte–Coxeter, le graphe de Foster et le graphe de Biggs-Smith.

Notes et références

1. (en) Norman Biggs, Algebraic Graph Theory, 2^d Edition, Cambridge University Press, 1993, 214 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 155
2. (en) Hajime Tanaka, Jack H. Koolen et Edwin R. van Dam, « Distance-regular graphs », The Electronic Journal of Combinatorics,‎ 23 octobre 2014, p. 20-21 (arXiv 1410.6294, lire en ligne, consulté le 2 juillet 2019)
3. (en) Eric W. Weisstein, « Distance-Transitive Graph », sur mathworld.wolfram.com (consulté le 2 juillet 2019)
4. (en) N. L. Biggs et D. H. Smith, « On Trivalent Graphs », Bulletin of the London Mathematical Society, vol. 3, n^o 2,‎ 1971, p. 155–158 (ISSN 1469-2120, DOI 10.1112/blms/3.2.155, lire en ligne, consulté le 2 juillet 2019)