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 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

      Identifiers