Graphe distance-unité

En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe pouvant être représenté par un ensemble de points du plan euclidien en reliant par une arête uniquement des paires de points distants d'une unité ; s'il existe une représentation où toutes les paires de points à distance 1 sont reliées, on parle de graphe distance-unité strict^[1].

Le graphe de Petersen est un graphe distance-unité : il peut être tracé sur le plan avec des arêtes toutes de longueur 1.

Les arêtes peuvent se croiser, si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. Si une représentation est sans croisement entre les arêtes, toutes de longueur 1, alors le graphe est qualifié de graphe-allumettes.

Exemples

• Les graphes chaine, les graphes grille, les graphes cycle, les graphes étoile.
• Les graphes prisme, dont le graphe cube, et les graphes hypercube, dont le graphe tesseract.
  • 
    Graphe prisme triangulaire.
  • 
    Graphe cube, à la fois graphe prisme et graphe hypercube.
  • 
    Graphe prisme pentagonal.
  • 
    Graphe hypercube Q₄ ou graphe tesseract, à 16 sommets et 32 arêtes.

• Le graphe de Petersen ainsi que ceux de Moser, de Harborth et de Golomb.
  • 
    Graphe de Petersen.
  • 
    Graphe de Moser.
  • 
    Graphe de Harborth, graphe-allumettes.
  • 
    Graphe de Golomb.
• à 4 sommets : le graphe diamant, le graphe griffe, le graphe patte.
• à 5 sommets : le graphe papillon, le graphe taureau, le graphe criquet, le graphe fléchette, le graphe cerf-volant, le graphe fourche, le graphe maison, le graphe bannière.
• à 6 sommets : le graphe poisson, le graphe croix, le graphe mite.
• à 7 sommets : le graphe roue W₇ (c'est le seul graphe roue à être distance-unité), le graphe longhorn.

Dénombrements

Classement par nombre de sommets

Le nombre ${\displaystyle a(n)}$ de graphes distance-unités connexes à ${\displaystyle n}$ sommets à isomorphisme près est donné par la suite A059103 de l'OEIS^[2].

${\displaystyle n}$	1	2	3	4	5	6
${\displaystyle a(n)}$	1	1	2	5	13	51

Nombre maximal d'arêtes

Le graphe roue W₇ est un graphe distance-unité à 7 sommets ayant un maximum d'arêtes (12).

Paul Erdős posa le problème suivant en 1946 : quel est le nombre maximal ${\displaystyle g(n)}$ d'occurrences d'une distance donnée (pouvant être prise égale à 1) déterminée par ${\displaystyle n}$ points dans le plan ?^[3] En d'autres termes quel est le nombre maximal d'arêtes d'un graphe distance-unité à ${\displaystyle n}$ sommets ?

Les valeurs de ${\displaystyle g(n)}$ sont connues jusqu'à ${\displaystyle n=14}$ (suite A186705 de l'OEIS) :

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14
${\displaystyle g(n)}$	0	1	3	5	7	9	12	14	18	20	23	27	30	33

Jusqu'à ${\displaystyle n=8}$, les graphes correspondants peuvent être tracés dans le réseau hexagonal, mais ce n'est plus le cas ensuite^[4].

Le graphe hypercube fournit un minorant de ${\displaystyle g(n)}$ proportionnel à ${\displaystyle n\ln n}$.

En considérant des points dans une grille carrée avec un espacement soigneusement choisi, Erdős a trouvé un meilleur minorant égal à : $${\displaystyle n^{1+c/\ln \ln n}}$$ pour une constante ${\displaystyle c}$^[3], et a offert 500 $ pour une preuve montrant que le nombre ${\displaystyle g(n)}$ peut également être majoré par une fonction de cette forme^[5].

Ce problème est très lié au théorème de Szemerédi-Trotter.

Application au nombre chromatique du plan

Le problème de Hadwiger-Nelson, introduit en 1944 par Hugo Hadwiger et Edward Nelson, concerne le nombre minimal de couleurs qu'il faut pour colorier le plan de façon que deux points à une distance de 1 ne soient jamais de la même couleur^[6]. Il peut être formalisé en théorie des graphes de la façon suivante : quel est le nombre chromatique maximal d'un graphe distance-unité ? Le problème est toujours ouvert mais le graphe de Golomb, avec son nombre chromatique égal à 4, fournit une borne inférieure^[7]. Un autre exemple connu, plus petit mais avec le même nombre chromatique, est le graphe de Moser^[8]. Cependant, en avril 2018, des graphes de nombre chromatique 5 (comportant plusieurs milliers de sommets, le plus petit a 1581 sommets) ont été découverts par Aubrey de Grey et contrôlés par ordinateur^[9],[10].

Généralisation

La notion de dimension d'un graphe reprend l'idée d'un graphe tracé avec des arêtes de longueur 1, mais ne se restreint pas au plan.