# 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

##### MSC:
 05C99 Graph theory 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
##### Keywords:
strong decomposability; strongly decomposable graph