The reduction of graph families closed under contraction (Q1126283)
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 955145
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The reduction of graph families closed under contraction |
scientific article; zbMATH DE number 955145 |
Statements
The reduction of graph families closed under contraction (English)
0 references
20 July 1997
0 references
A non-empty family \(\gamma\) of graphs is said to be closed under contraction if for all graphs \(G\) in the family \(\gamma\) and all edges \(e\) of \(G\), the contraction \(G/e\) belongs to \(\gamma\), provided that the definition of contraction \(G/H\) (\(H\) denotes a non-empty subgraph of \(G\)) says that the contraction \(G/H\) is the graph obtained from \(G\) by contracting all edges in \(H\) and by deleting any resulting loops. Introducing the concepts of a complete family, a free family and a kernel of a family, the author establishes a lot of very interesting properties concerning the three concepts. He concludes by developing a reduction method using contractions to find when a given graph belongs to a family \(\gamma\).
0 references
graph families
0 references
contraction
0 references
reduction
0 references
0.89768434
0 references
0.88516355
0 references
0.8845278
0 references
0.87148845
0 references
0.87146544
0 references
0 references
0.86964923
0 references
0.8676487
0 references
