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.

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 |