Ptolemaic graph

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs. A graph is Ptolemaic if and only if it obeys any of the following equivalent conditions: The shortest path distances obey Ptolemy's inequality: for every four vertices u, v, w, and x, the inequality d(u,v)d(w,x) + d(u,x)d(v,w) ≥ d(u,w)d(v,x) holds. For instance, the gem graph (3-fan) in the illustration is not Ptolemaic, because in this graph d(u,w)d(v,x) = 4, greater than d(u,v)d(w,x) + d(u,x)d(v,w) = 3. For every two overlapping maximal cliques, the intersection of the two cliques is a separator that splits the differences of the two cliques. In the illustration of the gem graph, this is not true: cliques uvy and wxy are not separated by their intersection, y, because there is an edge vw that connects the cliques but avoids the intersection. Every k-vertex cycle has at least 3(k − 3)/2 diagonals. The graph is both chordal (every cycle of length greater than three has a diagonal) and distance-hereditary (every connected induced subgraph has the same distances as the whole graph). The gem shown is chordal but not distance-hereditary: in the subgraph induced by uvwx, the distance from u to x is 3, greater than the distance between the same vertices in the whole graph. Because both chordal and distance-hereditary graphs are perfect graphs, so are the Ptolemaic graphs. The graph is chordal and does not contain an induced gem, a graph formed by adding two non-crossing diagonals to a pentagon. The graph is distance-hereditary and does not contain an induced 4-cycle. The graph can be constructed from a single vertex by a sequence of operations that add a new degree-one (pendant) vertex, or duplicate (twin) an existing vertex, with the exception that a twin operation in which the new duplicate vertex is not adjacent to its twin (false twins) can only be applied when the neighbors of the twins form a clique.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (4)

Related people (2)

Related concepts (6)

Block graph

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique. Block graphs are sometimes erroneously called Husimi trees (after Kôdi Husimi), but that name more properly refers to cactus graphs, graphs in which every nontrivial biconnected component is a cycle. Block graphs may be characterized as the intersection graphs of the blocks of arbitrary undirected graphs.

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.

Distance-hereditary graph

In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph. Distance-hereditary graphs were named and first studied by , although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs.

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

Circular Ones Matrices and the Stable set Polytopes of Quasi-Line Graphs

Friedrich Eisenbrand, Gautier Stauffer

2005