Leimer, H. G. 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 Cited in 4 Documents MSC: 05C99 Graph theory 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:strong decomposability; strongly decomposable graph Citations:Zbl 0656.00008 PDFBibTeX XML