Graphe de Franklin

Graphe de Franklin
Graphe de Franklin
Représentation du graphe de Franklin.
Représentation du graphe de Franklin.
Nombre de sommets 12
Nombre d'arêtes 18
Distribution des degrés 3-régulier
Rayon 3
Diamètre 3
Maille 4
Automorphismes 48 (Z/2Z×S4)
Nombre chromatique 2
Indice chromatique 3
Propriétés Cubique
Hamiltonien
Biparti
Sans triangle
Parfait
Sommet-transitif
modifier Consultez la documentation du modèle

Le graphe de Franklin est, en théorie des graphes, un graphe 3-régulier possédant 12 sommets et 18 arêtes.

Sommaire

Propriétés

Propriétés générales

Le diamètre du graphe de Franklin, 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 4. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

Coloriage

Le nombre chromatique du graphe de Franklin 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 mais ce nombre est minimal. Il n'existe pas de 1-coloration valide du graphe.

L'indice chromatique du graphe de Franklin est 3. Il existe donc une 3-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.

Il est possible de compter les colorations distinctes d'un graphe. Cela donne une fonction dépendant du nombre de couleurs autorisé. Cette fonction est polynomiale et est qualifiée de polynôme chromatique du graphe. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs à 2 et est de degrés 12. Il est égal à : (x − 1)x(x10 − 17x9 + 136x8 − 677x7 + 2338x6 − 5895x5 + 11059x4 − 15311x3 + 15005x2 − 9393x + 2839).

Propriétés algébriques

Le groupe d'automorphismes du graphe de Franklin est un groupe d'ordre 48 isomorphe à Z/2Z×S4, le produit direct du groupe symétrique S4 et du groupe cyclique Z/2Z.

Le polynôme caractéristique du graphe de Franklin est : (x − 3)(x − 1)3(x + 1)3(x + 3)(x2 − 3)2.

Voir aussi

Liens internes

Liens externes

Références



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Franklin de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Vent — Pour les articles homonymes, voir Vent (homonymie). Le vent est le mouvement d’une atmosphère, masse de gaz située à la surface d une planète. Les vents les plus violents connus ont lieu sur Neptune et sur Saturne. Il est essentiel à tous les… …   Wikipédia en Français

  • Music of ancient Greece — Apollo with the tortoise shell lyre, on a 5th century BC drinking cup (kylix) The music of ancient Greece was almost universally present in society, from marriages and funerals to religious ceremonies, theatre, folk music and the ballad like… …   Wikipedia

  • Doric Greek — Distribution of Greek dialects in the classical period.[1] Western group …   Wikipedia

  • Historia de la democracia — Las democracias modernas, como gobierno de la mayoría de la población, comenzaron a aparecer en la segunda mitad del siglo XIX junto con el sufragio universal, luego de la abolición generalizada de la esclavitud y la sanción de constituciones que …   Wikipedia Español

  • OCÉANOGRAPHIE — Définie traditionnellement comme l’«ensemble des disciplines scientifiques spécialisées dans l’étude de l’océan» (Vocabulaire de l’océanographie , 1976), l’océanographie apparaît plus que jamais comme une activité pluridisciplinaire dans laquelle …   Encyclopédie Universelle

  • VIE — «Qui sait si la première notion de biologie que l’homme a pu se former n’est point celle ci: il est possible de donner la mort.» Cette réflexion de Valéry dans son Discours aux chirurgiens (1938) va plus loin que sa destination première. Peut… …   Encyclopédie Universelle

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”