Degree restricted spanning trees of graphs

ABSTRACT

Let G = (V, E) be a connected graph and X be a vertex subset of G. Let f be a mapping from X to the set of natural numbers such that f(x) ≥ 2 for all x σ X. A degree restricted spanning tree is a spanning tree T of G such that f(x) ≤ deg_T(x) for all x σ X, where deg_T(x) denotes the degree of a vertex x in T. In this paper, we show that the decision problem "whether there exists a degree restricted spanning tree in G" is NP-complete. We also give a restricted proof of a conjecture, provided by Kaneko and Yoshimoto, on the existence of such a spanning tree in general graphs. Finally, we present a polynomial-time algorithm to find a degree restricted spanning tree of a graph satisfying the conditions presented in the restricted proof of the conjecture.

REFERENCES

• 1: Akiyama, J., and Kano, M. Factors and Factorizations of graphs - A survey. J. Graph Theory, 9 (1985), 1--42.
• 2: T. Böhme , H. J. Broersma , F. Göbel , A. V. Kostochka , M. Stiebitz, Spanning trees with pairwise nonadjacent endvertices, Discrete Mathematics, v.170 n.1-3, p.219-222, June 10, 1997 [doi>10.1016/S0012-365X(96)00306-8]
• 3: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: Hall, P. On representation of subsets. J. London Math Soc., 10 (1935), 26--30.
• 5: Hopcraft, J., and Karp, R. M., An O (n2.5) algorithm for maximum matching in bipartite graphs. SIAM J. Computing, 2 (1973), 225--231.
• 6: Atsushi Kaneko , Kiyoshi Yoshimoto, On spanning trees with restricted degrees, Information Processing Letters, v.73 n.5-6, p.163-165, March 2000 [doi>10.1016/S0020-0190(00)00018-1]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
Hamiltonian path, NP-completeness, algorithms, graphs, spanning trees