# zbMATH — the first resource for mathematics

K-terminal recursive families of graphs. (English) Zbl 0673.05081
Graph theory, 250th Anniv. Conf., Lafayette/Indiana 1986, Congr. Numerantium 63, 161-176 (1988).
Summary: [For the entire collection see Zbl 0663.00003.]
A graph $$G=(V,E,T)$$ is called a K-terminal graph if it has a specially designated subset $$T\subseteq V$$ of vertices, called terminals, where $$1\leq | T| \leq K$$. Given two K-terminal graphs $$G_ 1=(V_ 1,E_ 1,T_ 1)$$ and $$G_ 2=(V_ 2,E_ 2,T_ 2)$$, we consider a variety of ways of composing $$G_ 1$$ and $$G_ 2$$ to form a larger K- terminal graph, $$G=G_ 1\circ G_ 2=(V,E,T)$$, where $$T\subseteq T_ 1\cup T_ 2$$, and connections between $$G_ 1$$ and $$G_ 2$$ are established only between terminals in $$T_ 1$$ and terminals in $$T_ 2$$. Informally, K-terminal recursive graphs are families of graphs which can be constructed from a finite set of ‘basis’ graphs by repeatedly applying such K-terminal composition rules.
A wide variety of well-known families of graphs can be defined in this way, including trees, series-parallel graphs, outerplanar graphs, $$C_ N$$-trees, Halin graphs, cacti, $$K\times N$$ grid graphs, K-trees, and partial K-trees, for fixed K. It has been observed by many authors, that an impressively wide variety of NP-complete problems have linear time algorithm solutions when restriced to K-terminal recursive families of graphs.
Thus, if one can show that a given family of graphs is K-terminal recursive then immediately one can predict that literally dozens of linear time algorithms for solving NP-complete problems on such graphs are very likely to exist. This paper is a contribution to the development of a theoretical foundation for these families of graphs.

##### MSC:
 05C75 Structural characterization of families of graphs