Quasi-median graphs, their generalizations, and tree-like equalities
Let \(G\) be a graph with \(V(G)\) and \(E(G)\) denoting the sets of vertices and edges of \(G\), respectively. For an edge \(ab\) of \(G\), set \( W_{ab}=\{x\in V(G):d(x,a)<d(x,b)\}\) and \(U_{ab}=\{x\in W_{ab}:x\) has a neighboor \(y\) in \(W_{ba}\}.\) \(G\) is called quasi-median if every clique in \(G\) is gated and for any edge \(ab\), \(U_{ab}\) is convex. The paper presents three characterizations of quasi-median graphs and also proves two equalities for these graphs. Finally, an Euler formula is derived for graphs that can be obtained by a sequence of connected expansions from \( K_{1}\).
scientific article; zbMATH DE number 1957117
scientific article