A forbidden subgraph characterization of some graph classes using betweenness axioms. (English) Zbl 1262.05106

Changat, Manoj; Lakshmikuttyamma, Anandavally K.; Mathews, Joseph; Peterin, Iztok; Narasimha-Shenoi, Prasanth G.; Seethakuttyamma, Geetha; Špacapan, Simon

Discrete Math. 313, No. 8, 951-958 (2013).

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

Keywords:

forbidden subgraphs; induced path; interval function; betweenness axioms; chordal graphs; distance hereditary graphs