×

zbMATH — the first resource for mathematics

A forbidden subgraph characterization of some graph classes using betweenness axioms. (English) Zbl 1262.05106
Summary: Let \(I_G(x,y)\) and \(J_G(x,y)\) be the geodesic and induced path intervals between \(x\) and \(y\) in a connected graph \(G\), respectively. The following three betweenness axioms are considered for a set \(V\) and \(R:V\times V\to 2^V\):
(i)
\(x\in R(u,y)\), \(y\in R(x,v)\), \(x \neq y\), \(|R(u,v)| > 2 \Rightarrow x \in R(u,v)\);
(ii)
\(x\in R(u,v) \Rightarrow R(u,x) \cap R(x,v) =\{x\}\);
(iii)
\(x\in R(u,y)\), \(y \in R(x,v)\), \(x \neq y \Rightarrow x \in R(u,v)\).
We characterize the class of graphs for which \(I_G\) satisfies (i), the class for which \(J_G\) satisfies (ii) and the class for which \(I_G\) or \(J_G\) satisfies (iii). The characterization is given in terms of forbidden induced subgraphs. It turns out that the class of graphs for which \(I_G\) satisfies (i) is a proper subclass of distance hereditary graphs and the class for which \(J_G\) satisfies (ii) is a proper superclass of distance hereditary graphs. We also give an axiomatic characterization of chordal and Ptolemaic graphs.

MSC:
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C12 Distance in graphs
05C75 Structural characterization of families of graphs
PDF BibTeX XML Cite
Full Text: DOI