Puissances de graphes

Problèmes extrémaux 

 Considérons un réseau social, comme les réseaux Facebook, Twitter ou MSN. Supposons qu’à un instant donné, chaque personne ajoute comme amis les amis de ses amis : alors un certain nombre de nouvelles amitiés (connexions) vont se créer dans le réseau. Peut-on évaluer le nombre minimal de connexions qui seront créées, et le nombre minimal d’amitiés qui existeront au final ? Quels sont les cas extrémaux ? On peut aussi répéter l’opération plusieurs fois avant d’envisager ces questions. Ces différents problèmes se formulent naturellement en termes de puissances de graphes. Voici précisément ce que nous nous proposons d’étudier : Questions (I) Quelle est la taille maximale d’un graphe G d’ordre n de diamètre d ? (II) Quelle est la taille minimale de la puissance r-ième d’un graphe G connexe d’ordre n ? (III) Étant donné un graphe connexe G d’ordre n et de diamètre d > r, quelle est la valeur minimale de |E(G r )| − |E(G)| , autremement dit combien d’arêtes sont ajoutées au minimum quand on passe de G à sa puissance r-ième ? Dans chaque cas, nous cherchons la liste exhaustive des graphes réalisant l’extremum. Nous envisagerons ensuite, dans la section 5.4, ces questions dans le cas des graphes orientés. 5.2 État des lieux Un théorème d’Ore donne la réponse à la question (I) : Théorème 5.1 (Ore [79]). Soit G un graphe d’ordre n et de diamètre d ≥ 2. Alors la taille de G vérifie |E(G)| ≤ n(n − 1) 2 − b(n, d − 1) − 1, où b(n, r) = (r − 1)(n − 1 − r 2 ). Autrement dit, quel que soit r ≥ 1, si le nombre d’arêtes qui manquent à un graphe d’ordre n pour être complet est inférieur ou égal à b(n, r), alors son diamètre est au plus r, i.e. Gr est complet. Ore caractérise aussi les graphes réalisant l’égalité dans le théorème 5.1, c’est-à-dire les graphes de diamètre fixé ayant le plus d’arêtes possible. Nous retrouvons ce résultat comme conséquence de notre réponse à la question (III), mais il peut être intéressant de considérer dès maintenant ces graphes extrémaux. Pour cela, nous appelons chaîne de cliques de longueur q et notons (W0, W1, · · · , Wq) un graphe G (voir fig. 5.I) tel que : – les ensembles W0, W1, · · · , Wq forment une partition de V (G) ; – pour tout i vérifiant 0 ≤ i ≤ q − 1 le graphe G[Wi ∪ Wi+1] est une clique ; – si i + 1 < j, il n’y a aucune arête entre Wi et Wj . On peut construire toute chaîne de cliques de longueur q en partant d’une chaîne de longueur q et en remplaçant chaque sommet par une clique, reliant entre eux tous les sommets de deux cliques correspondant à des sommets initialement adjacents. Le diamètre d’une telle chaîne de clique est égal à q.cliques toutes les arêtes Figure 5.I – Une chaîne de cliques, cas non orienté Avec ce vocabulaire, les graphes extrémaux correspondant à la question (I) sont aisément décrits. Il convient de distinguer les graphes diamètre-critiques, pour lesquels l’ajout de toute arête diminuerait strictement le diamètre, et les graphes maximum diamètrecritiques, qui de plus ont le nombre maximum d’arêtes possible (et qui sont précisément ceux qui nous intéressent dans le cadre de la question (I)) : Théorème 5.2 (Ore [79]). Pour tout d ≥ 2, un graphe de diamètre d est diamètre-critique si et seulement s’il est une chaîne de cliques de longueur d, et est maximum diamètrecritique si et seulement s’il est une chaîne de cliques de longueur d où toutes les cliques sont réduites à un seul sommet, sauf éventuellement deux cliques consécutives ne pouvant se trouver aux extrémités de la chaîne de cliques. 

Nouveaux résultats dans le cas non orienté

La question (I), comme précisé ci-avant, a été entièrement résolue par Ore ([79]). Pour la question (II), nous avons caractérisé les graphes réalisant l’extremum, complétant ainsi le théorème 5.3 : Théorème 5.5 (Auger, Charon, Hudry, Lobstein [11] & appendice H). Soit r ≥ 1 et G un graphe connexe d’ordre n ≥ 1 et de diamètre d < r. Alors |E(G r )| = nr − r(r + 1) 2 si et seulement si G est une chaîne. 5.4 Nouveaux résultats dans le cas orienté 56 Ce résultat est aussi une conséquence du théorème 5.6, qui répond à la question (III). Le voici : Théorème 5.6 (Auger, Charon, Hudry, Lobstein [11] & appendice H). Soit r ≥ 1. Si G est un graphe connexe d’ordre n et de diamètre au moins r + 1, alors |E(G r )| − |E(G)| ≥ b(n, r), où b(n, r) = (r − 1)(n − 1 − r 2 ). Si Gr n’est pas complet alors G gagne donc au moins b(n, r) arêtes lorsqu’il est élevé à la puissance r, et donc le nombre d’arêtes qui manquent à G pour être complet est strictement supérieur à b(n, r). On retrouve ainsi le théorème 5.1. Décrivons maintenant les graphes pour lesquels il y a égalité, en termes de chaînes de cliques (cf. section 5.2). Théorème 5.7 (Auger, Charon, Hudry, Lobstein [11] & appendice H). Les seuls graphes réalisant l’égalité dans le théorème 5.6 sont les chaînes de cliques (W0, W1, · · · , Wq) appartenant à l’un des types suivants : – type 1 : q = r + 1 et il existe au plus deux entiers j tels que |Wj | > 1, qui doivent alors être consécutifs. – type 2 : q ≥ r + 1 et |Wi | = 1 dès que 2 ≤ i ≤ q − 2 ; de plus si q = r + 1 alors |W1| = 1 et |Wq−1| = 1, et si q = r + 2 alors |W1| = 1 ou |Wq−1| = 1. Notons que le théorème 5.5 est une conséquence immédiate des théorèmes 5.6 et 5.7, car on vérifie que n − 1 + b(n, r) = nr − r(r + 1) 2 . Ainsi, un graphe réalisant l’extremum du théorème 5.5 est nécessairement une chaîne de cliques ayant exactement n − 1 arêtes, et ne peut donc être qu’une chaîne. Les graphes décrits dans le théorème 5.7 sont aisément compris avec une description conditionnelle : ce sont les chaînes de cliques (W0, W1, · · · , Wq) avec q ≥ r + 1 telles qu’un sommet d’une clique Wi vérifiant |Wi | ≥ 2 admette dans le graphe exactement un sommet à distance k pour tout k vérifiant 2 ≤ k ≤ r. Parmi les graphes de type 1, on retrouve les graphes maximum diamètre-critiques évoqués dans la section précédente (théorème 5.2, voir la fig. 5.II pour un exemple) puisqu’il leur manque exactement b(n, r) + 1 arêtes pour êtres complets et qu’il ne manque qu’une seule arête à leur puissance r-ième pour être un graphe complet. À ces graphes s’ajoutent ceux de type 1 ayant une clique comportant plus d’un sommet sur une clique extrême (voir un exemple sur la figure 5.III), ainsi que ceux de type 2. Les différentes possibilités pour les graphes de type 2 sont illustrées sur la figure 5.IV. Notons que les deux types ne sont pas exclusifs.