Graphe de Robertson
- Graphe de Robertson
-
Le graphe de Robertson est, en théorie des graphes, un graphe 4-régulier possédant 19 sommets et 38 arêtes.
Propriétés
Propriétés générales
Le diamètre du graphe de Robertson, l'excentricité maximale de ses sommets, est 3, son rayon, l'excentricité minimale de ses sommets, est 3 et sa maille, la longueur de son plus court cycle, est 5. Il s'agit d'un graphe 4-sommet-connexe et d'un graphe 4-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 4 sommets ou de 4 arêtes.
Coloriage
Le nombre chromatique du graphe de Robertson est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 2-coloration valide du graphe.
L'indice chromatique du graphe de Robertson est 5. Il existe donc une 5-coloration des arêtes du graphe tels 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 groupe d'automorphismes du graphe de Robertson est un groupe d'ordre 24.
Le polynôme caractéristique du graphe de Robertson est : − (x − 4)(x − 1)2(x2 − 3)2(x2 + x − 5)(x2 + x − 4)2(x2 + x − 3)2(x2 + x − 1).
Voir aussi
Liens internes
Liens externes
Références
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Robertson de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe de Robertson-Wegner — Nombre de sommets 30 Nombre d arêtes 75 Distribution des degrés 5 régulier Rayon 3 Diamètre 3 Maille 5 Automorphismes 20 … Wikipédia en Français
Graphe Planaire — Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu aucune arête (ou arc pour un graphe orienté) n en croise une autre. Autrement dit, ces graphes sont précisément… … Wikipédia en Français
Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier … Wikipédia en Français
Graphe (mathématiques) — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français
Graphe (théorie des graphes) — Théorie des graphes Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… … Wikipédia en Français
Graphe planaire — Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu aucune arête (ou arc pour un graphe orienté) n en croise une autre. Autrement dit, ces graphes sont précisément… … Wikipédia en Français
Graphe toroïdal — Un graphe plongé sur le tore de telle façon que les arêtes ne se coupent pas. En mathématiques, et plus précisément en théorie des graphes , un graphe G est toroïdal s il peut être plongé sur le tore, c et à dire que les sommets du graphe peuvent … Wikipédia en Français
Graphe parfait — Théorème des graphes parfaits Sommaire 1 Contexte 2 Théorèmes 3 Intérêt 4 Notes 5 Références … Wikipédia en Français
Théorème de Robertson-Seymour — En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour (parfois également appelé le théorème des mineurs, et connu, avant qu il soit démontré, sous le nom de conjecture de Wagner), est un théorème démontré… … Wikipédia en Français
Hypercube (Graphe) — Pour les articles homonymes, voir Hypercube (homonymie). Cette page se comprend mieux après la lecture de Théorie des graphes. Hypercube … Wikipédia en Français
