Graphe ptolémaïque

vignette| Un graphe ptolémaïque. vignette| Le graphe gemme ou 3-fan n'est pas ptolémaïque. vignette|upright=1.4|Un graphe en bloc est un cas particulier d'un graphe ptolémaïque vignette|upright=1.4| Trois opérations qui permettent de construire tout graphe distance-héréditaire. Pour les graphes ptolémaïques, les voisins de « faux jumeaux » doivent former une clique, ce qui empêche la construction d'un cycle à 4 sommets, montré ici. En théorie des graphes, un graphe de Ptolémée ou graphe ptolémaïque est un graphe non orienté dont les distances des plus courts chemins entre sommets les plus courtes obéissent à l'inégalité de Ptolémée, qui à son tour a été nommée d'après l'astronome et mathématicien grec Ptolémée. Les graphes de Ptolémée sont exactement les graphes qui sont à la fois cordaux et à distance héréditaire ; ils incluent les graphes par blocs et sont une sous-classe des graphes parfaits. Un graphe est ptolémaïque si et seulement s'il vérifie une des conditions équivalentes suivantes : Les distances des chemins les plus courts vérifient l'inégalité de Ptolémée : quatre sommets quelconques , et vérifient l'inégalité Par exemple, le graphe gemme de l'illustration n'est pas ptolémaïque, car dans ce graphe L'intersection de deux cliques maximales chevauchantes est un séparateur qui sépare les différences des deux cliques. Dans le graphe gemme, ce n'est pas le cas : les cliques uvy et wxy ne sont pas séparées par leur intersection y, car l'arête vw relie les cliques et évite l'intersection. Tout cycle à k sommets a au moins diagonales. Le graphe est à la fois cordal (chaque cycle de longueur supérieure à trois a une diagonale) et à distance héréditaire (chaque sous-graphe induit connexe a les mêmes distances que le graphe tout entier). Le graphe gemme ci-dessus est cordal mais n'est pas à distance héréditaire : dans le sous-graphe induit par uvwx, la distance de u à x est de 3, et est donc supérieure à la distance entre les mêmes sommets dans le graphe entier.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (4)

Personnes associées (2)

Concepts associés (6)

Graphe de blocs

vignette|upright=1.4|Un graphe de blocs. En théorie des graphes, une branche des mathématiques combinatoires, un graphe de blocs ou arbre de cliques est un graphe non orienté dans lequel chaque composante biconnexe (ou « bloc ») est une clique. Les graphes de blocs ont été appelés aussi arbres Husimi (d'après Kôdi Husimi), mais ce nom fait plus référence aux graphes cactus, qui sont des graphes dans lesquels chaque composante biconnexe non triviale est un cycle.

Induced path

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.

Graphe à distance héréditaire

vignette| Exemple d'un graphe à distance héréditaire. En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits.

The stable set polytope of quasi-line graphs

Friedrich Eisenbrand, Gautier Stauffer

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...

2008

On the stable set polytope of claw-free graphs

Gautier Stauffer

In this thesis we focus our attention on the stable set polytope of claw-free graphs. This problem has been open for many years and albeit all the efforts engaged during those last three years, it is still open. This does not mean that no progress has been ...

EPFL2005

2005