Graph classes between parity and distance-hereditary graphs (Q1302157): Difference between revisions

We define operations \(\beta\), \(\gamma\) and \(\phi\) as follows: Let \(x\) be a vertex of a graph \(G\) and let \(y\) be a vertex of a graph \(H\) such that \(G=H-y\). Then \(H = \beta(G,x)\) if \(x\) and \(y\) are true twins (both vertices have the same closed neighbourhood in \(H\)), and \(H = \gamma(G,x)\) if \(x\) and \(y\) are false twins (both vertices have the same open neighbourhood in \(H\)). Now let \((X,Y,Z)\) be a partition of the vertex set of \(H\) such that \(G = H-Y\). Then \(H = \phi(G,B,X)\) if \(X\) is a set of false twins in \(G\) and \(X\) is contained in one color class of the bipartite graph \(B = H-Z\). Let \(C\) be a class of bipartite graphs closed under taking connected subgraphs. By \(\Phi_C\) we denote the hull of \(K_1\) under the operations \(\beta\), \(\gamma\) and \(\phi\), where \(B \in C\). If \(C\) is the class of all bipartite graphs then \(\Phi_C\) is the class of all parity graphs, and if \(C = \{K_2,K_1\}\) then \(\Phi_C\) is the class of all distance hereditary graphs. In general, the classes \(\Phi_C\), partially ordered by set inclusion, form a lattice of infinite height. Cunningham's split decomposition leads to characterizations of the \(\Phi_C\) classes that enable polynomial time algorithms for recognition and isomorphism test.