On forcibly hereditary P-graphical sequences

Let G and B be graphs and \(\Phi\) a surjective function from V(G) to V(B). If \(X\subseteq E(B)\), then \(\Phi^{-1}(X)=\{xy\in E(G)| \Phi (x)\Phi (y)\in X\}\). If \(\Phi\) has the property that for every uv\(\in E(B)\), \(\Phi^{-1}(\{uv\})\) is a perfect matching between \(\Phi^{-1}(u)\) and \(\Phi^{-1}(v)\), and for every uv\(\not\in E(B)\), \(u\neq v\), there is no edge between \(\Phi^{-1}(u)\) and \(\Phi^{-1}(v)\), then \(\Phi\) is called a pseudomorphism from G to B. Let G, B and F be graphs and suppose that \(\Phi\) is a pseudomorphism from G to B. Then G is said to be a semidirect product of B and F if the subgraph induced by \(\Phi^{-1}(v)\) is isomorphic to F for all \(v\in V(B)\). A graph G is semidecomposable if G is a semidirect product of two nontrivial graphs. The authors classify those graphs G for which G and \(\bar G\) are both semidecomposable.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: On forcibly hereditary P-graphical sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820175)