zbMATH — the first resource for mathematics

Triangulated graphs with marked vertices. (English) Zbl 0678.05056
Graph theory in memory of G. A. Dirac, Pap. Meet., Sandbjerg/Den. 1985, Ann. Discrete Math. 41, 311-324 (1989).
[For the entire collection see Zbl 0656.00008.]
This paper deals with decomposable and strongly decomposable graphs. The author succeeds in proving a criterion for the characterization of strong decomposability of a graph \(G=(V,E)\) by means of the decomposability of a modified graph \(G_ m=(V_ m,E_ m)\), where \(V=\Gamma \cup \Delta\), \(V_ m=V\cup \{m\}\), \(E_ m=E\cup \{\{d,m\},d\in \Delta \}\). Then he introduces further concepts in order to give some equivalent conditions for a decomposable or a strongly decomposable graph \(G=(V,E)\). H.-G. Leimer finishes by formulating a simple linear-time algorithm to test strong decomposability.
Reviewer: R.Bodendiek

05C99 Graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)