The induced path convexity, betweenness, and svelte graphs (Q1613551)

All graphs \(G= (V,E)\) considered in the paper are finite, simple, and connected. The set \(I(u,v)= \{w\in V\mid w\) lies on some \(u,v\)-geodesic\} is called the geodesic (i.e. shortest path) interval between \(u,v\in V\), and a subset \(W\) of \(V\) is said to be geodesically convex in \(G\) if, for any two vertices \(u,v\in W\), \(I(u,v)\subseteq W\) holds. The family of such sets in a graph forms a true convexity. \(w\) is said to be geodesically between \(u\) and \(v\) if \(w\in I(u,v)\), and thus \(I\) defines a ``proper betweenness'' in the following sense: if \(w\) is between \(u\) and \(v\) and \(w\) is distinct from \(u\) and \(v\), then \(v\) is not between \(u\) and \(v\). For a triple of vertices \(u\), \(v\), \(w\) in \(G\) let \(I(u,v,w)\) be defined by \(I(u,v,w)= I(u,v)\cap I(v,w)\cap I(w,u)\). In general \(|I(u,v,w)|= 0\) holds. The set \(J(u,v)= \{w\in V\mid w\) lies on some induced \(u,v\)-path\} is called the induced path interval between \(u,v\in V\), and a subset \(W\) of \(V\) is said to be a induced-path convex if, for any two vertices \(u,v\in W\), \(J(u,v)\subseteq W\) holds. The family of such sets in a graph forms a true convexity. Now a notion of betweenness is introduced by a betweenness relation \(B\subseteq X\times X\times X\) on a set \(X\) satisfying four conditions; here the first three axioms are just the translation of the word ``between'' into mathematics, and the fourth axiom is a kind of transitivity. \(w\) is said to be between \(u\) and \(v\) if \((u,w,v)\in B\). The geodesic betweenness \(B_I\), defined by \((u,w,v)\in B_I\) if \(w\in I(u,v)\), satisfies the above conditions, but the relation \(B_J\), defined by \((u,w,v)\in B_J\) if \(w\in J(u,v)\), in general is not a betweenness relation in the above sense. Also it follows that for the intersection of intervals between pairs of a triple \(J(u,v,w)= J(u,v)\cap J(v,w)\cap J(w,u)\) in general \(|J(u,v,w)|\neq 0\) holds. For the case of small sets \(J(u,v,w)\) the notion ``svelte graph'' is introduced: A connected graph \(G\) is called svelte graph if \(|J(u,v,w)|\leq 1\), for all triples \(u,v,w\in G\). In the present paper, among other things, properties of the geodesic and of the induced-path intervals are investigated. An abstract notion of betweenness is introduced and characterized, the intersection of induced-path intervals between the pairs of a triple of vertices is discussed and some graphs are characterized. The following results are given: Let \(G= (V,E)\) be a connected graph. Then (i) the relation \(B_J\subseteq V\times V\times V\) defined by \((u,w,v)\in B_J\) if \(w\in J(u,v)\) is a betweenness relation iff \(G\) does not contain three given forbidden graphs as induced subgraphs (Theorem 2); (ii) \(|J(u,v,w)|= 0\), for any triple of distinct vertices \(u\), \(v\), \(w\), iff \(G\) is a complete graph (Proposition 3); (iii) \(|J(u,v,w)|\leq 1\), for any triple of vertices \(u\), \(v\), \(w\), iff \(G\) does not contain given forbidden graphs as induced subgraphs (figures are given in the paper) (Theorem 6 and main result of the paper, with a very extensive proof); and (iv) \(|J(u,v,w)|= 1\), for any triple of vertices \(u\), \(v\), \(w\), iff every block (maximal 2-connected subgraph) in \(G\) is \(K_2\) or a 4-cycle (Proposition 4). Finally, four conditions are given which are equivalent statements (Theorem 9).