# 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
Full Text: