No label defined (Q3032302)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4130433
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4130433 |
Statements
1988
0 references
family of graphs
0 references
contraction
0 references
0.888126790523529
0 references
0.7890903353691101
0 references
0.7730756402015686
0 references
0.7643605470657349
0 references
[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).]
0 references