Voir la source de 110-graphe de Iofinova-Ivanov

{{Infobox Graphe
 | nom                = 110-Graphe de Iofinova-Ivanov
 | image              = 
 | légende            = 
 | distribution       = 3-[[Graphe régulier|régulier]]
 | sommets            = 110
 | arêtes             = 165
 | automorphismes     = 1320
 | maille             = 10
 | diamètre           = 7
 | rayon              = 7
 | nombre chromatique = 2
 | indice chromatique = 3
 | propriétés         = [[Graphe arête-transitif|Arête-transitif]]<br />[[Graphe biparti|Biparti]]<br />[[Graphe cubique|Cubique]]<br />[[Graphe hamiltonien|Hamiltonien]]<br />[[Graphe régulier|Régulier]]
}}
Le '''110-graphe de Iofinova-Ivanov''' est, en [[théorie des graphes]], un [[graphe régulier|graphe 3-régulier]] possédant 110 sommets et 165 arêtes.

== Propriétés ==
Iofinova et Ivanov ont montré en 1985 qu'il existe exactement cinq graphes semi-symétriques cubiques [[Graphe biparti|bipartis]] (bipartite cubic semisymmetric graphs) dont le groupe d'automorphisme préserve les [[Partition (mathématiques)|partition]]s et agit primitivement sur chaque partition. Le plus petit graphe possède 110 sommets, les autres ont 126, 182, 506 et 990 sommets<ref>[http://mathworld.wolfram.com/Iofinova-IvanovGraphs.html Graphes de Iofinova-Ivanov sur mathworld.wolfram.com]</ref>.

=== Propriétés générales ===
Le [[Diamètre (théorie des graphes)|diamètre]] du 110-graphe de Iofinova-Ivanov, l'excentricité maximale de ses sommets, est 7, son [[Rayon (théorie des graphes)|rayon]], l'excentricité minimale de ses sommets, est 7 et sa [[Maille (théorie des graphes)|maille]], la longueur de son plus court [[cycle (graphe)|cycle]], est 10. Il s'agit d'un graphe 3-[[Graphe sommet-connexe|sommet-connexe]] et d'un graphe 3-[[Graphe arête-connexe|arête-connexe]], c'est-à-dire qu'il est [[graphe connexe|connexe]] et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

=== Coloration ===
Le [[nombre chromatique]] du 110-graphe de Iofinova-Ivanov est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'[[indice chromatique]] du 110-graphe de Iofinova-Ivanov est 3. Il existe donc une 3-coloration des arêtes du graphe telles que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

=== Propriétés algébriques ===
Le [[polynôme caractéristique]]  de la [[matrice d'adjacence]] du 110-graphe de Iofinova-Ivanov est : <math>(x-3) x^{20} (x+3) (x^4-8 x^2+11)^{12} (x^4-6 x^2+6)^{10}</math>.

== Références ==
{{Références}}

== Voir aussi ==
=== Bibliographie ===
* {{en}} Iofinova, M. E. et Ivanov, A. A. ''Bi-Primitive Cubic Graphs.'' In ''Investigations in the Algebraic Theory of Combinatorial Objects''. pp. 123-134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137-152, 1985.)
* {{en}} Ivanov, A. A. ''Computation of Lengths of Orbits of a Subgroup in a Transitive Permutation Group.'' In ''Methods for Complex System Studies''. Moscow: VNIISI, pp. 3-7, 1983.
* {{en}} Ivanov, A. V. ''On Edge But Not Vertex Transitive Regular Graphs.'' In ''Combinatorial Design Theory'' (Ed. C. J. Colbourn and R. Mathon). Amsterdam, Netherlands: North-Holland, pp. 273-285, 1987. 

=== Liens externes ===
* {{en}} [[Eric W. Weisstein]], [http://mathworld.wolfram.com/Iofinova-IvanovGraphs.html Iofinova-Ivanov Graphs] ([[MathWorld]])


{{Portail|Mathématiques}}

[[Catégorie:Graphe remarquable|Iofinova-Ivanov (110)]]