scientific article; zbMATH DE number 4130433
[For the entire collection see Zbl 0665.00002.] A family of graphs will be called a family. We say that a family \({\mathcal F}\) is closed under contraction if for any \(G\in {\mathcal F}\) and any connected subgraph \(H\subseteq G\), G/H\(\in {\mathcal F}.\) For any family \({\mathcal C}\) whose members are connected, a \({\mathcal C}\)- reduction of G is a graph obtained from G by repeated contractions of subgraphs in \({\mathcal C}\) until the resulting graph has no nontrivial subgraph in \({\mathcal C}.\) Let \({\mathcal S}\) and \({\mathcal C}\) be graph families closed under contraction such that all graphs in \({\mathcal C}\) are connected and \({\mathcal C}\)- reductions are unique. In this paper, we present interesting examples of such families \({\mathcal S}\) and \({\mathcal C}\) for which the following equivalence holds for every graph G: \[ G\in {\mathcal S} \Leftrightarrow \text{ The \({\mathcal C}\)-reduction of G is in }{\mathcal S}. \] For mod families \({\mathcal S}\), this equivalence holds only if \({\mathcal C}=\{K_ 1\}\), a trivial case, but we present nontrivial instances. [For the notation see \textit{J. A. Bondy} and \textit{M. S. R. Murty}, Graph Theory and Applications, New York (1976).]
- A new reduction rule for the connection graph proof procedure
- An algorithm for transitive reduction of an acyclic graph
- Duality in graph families
- A method of graph reduction and its applications
- A reduction algorithm meeting users' requirements.
- Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
- scientific article; zbMATH DE number 4073031 (Why is no real title available?)
- scientific article; zbMATH DE number 124283 (Why is no real title available?)
- An algebraic theory of graph reduction
- Contractions of stars in bipartite graphs
- scientific article; zbMATH DE number 6664202 (Why is no real title available?)
- scientific article; zbMATH DE number 2208652 (Why is no real title available?)
- On the reduction of Yutsis graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3032302)