On forcibly hereditary P-graphical sequences
type: Item
instance of: scholarly article
title: On forcibly hereditary P-graphical sequences
zbMATH Open document ID: 0614.05047
DOI: 10.1016/0012-365X(87)90184-1
author: A. A. Chernyak
author: Zhanna A. Chernyak
author: Regina Iosifovna Tyshkevich
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3993633
zbMATH Keywords: pseudomorphism
zbMATH Keywords: semidirect product
zbMATH Keywords: semidecomposable
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
cites work: Q3942982
cites work: Linear Separation of Dominating Sets in Graphs
cites work: Q3039401
cites work: Q4165164
cites work: Integer-pair sequences with self-complementary realizations
cites work: Characterizations of strongly chordal graphs
cites work: Q4193514
cites work: Some Properties of Graphs with Multiple Edges
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Trivially perfect graphs
cites work: The complexity of comparability graph recognition and coloring
cites work: Q3207000
cites work: Threshold Sequences
cites work: The splittance of a graph
cites work: A Note on Unigraphic Sequences
cites work: Structure and recognition of domishold graphs
cites work: Solution of the Hamiltonian problem for self-complementary graphs
cites work: Q3929766
cites work: Q3937454
cites work: Q3870938
cites work: Once more on matrogenic graphs
cites work: Q3874253
cites work: Q3852226
cites work: Q3743346
cites work: Q3698836
cites work: Graphs and degree sequences: Canonical decomposition
cites work: On the existence of N‐connected graphs with prescribed degrees (n ≧ 2)
description: scientific article; zbMATH DE number 3993633