NP-completeness and degree restricted spanning trees

✍ Scribed by Robert James Douglas

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 449 KB
• Volume: 105
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90130-8

✦ Synopsis

In this paper several results are proved: (1) Deciding whether a given planar graph G with maximum degree 3 has a spanning tree T, where deg(x, T) = 1 or 3 for each node x, is NP-Complete.

(2) For each proper subset S of the positive integers Z+ with 1 E S and (S( 2 2, deciding whether a planar graph G = (V, E) has a spanning tree T such that deg(x, T) E S, for all x E V, is NP-Complete.

(3) For each non-empty proper subset S of Z*, deciding whether, given a planar graph G = (V, E) and integer N with 1 s N < IVI, there is a spanning tree T for G such that T has at least [at most] N nodes x with deg(x, T) ES is NP-complete.

Also, as corollaries of (1)) we show that for a planar graph G , with n nodes and maximum degree 3, it is NP-complete to decide (4) if there is a spanning tree with at least [exactly] n/2 + 1 leaves and (5) if G has a connected dominating set with cardinality <n/2 -1.