摘要
Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V 1, V 2, ..., V k) of V(G) such that for each i(1≤i≤k), G[V i] is 1-regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows: Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP-complete; induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.
Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V 1, V 2, ..., V k) of V(G) such that for each i(1≤i≤k), G[V i] is 1-regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows: Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP-complete; induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.
基金
Supported by the National Natural Science Foundation of China( 1 0 371 1 1 2 ) and the Natural ScienceFoundation of Henan( 0 4 1 1 0 1 1 2 0 0 )
