| PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS |
| |
| 作者姓名： | Yang Aifeng Yuan Jinjiang Dept. of Appl. Math. South China Univ. of Tech. Guangdong China. Dept. of Math. Zhengzhou Univ. Henan China. |
| |
| 作者单位： | Yang Aifeng 1，2 Yuan Jinjiang 21 Dept. of Appl. Math.，South China Univ. of Tech.，Guangdong 510640，China. 2 Dept. of Math.，Zhengzhou Univ.，Henan 450052，China. |
| |
| 基金项目： | 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 ) |
| |
| 摘 要： | §1 IntroductionGraphs considered in this paper are finite and simple.For a graph G,its vertex setandedge set are denoted by V(G) and E(G) ,respectively.If vertices u and v are connected inG,the distance between u and v,denoted by d G(u,v) ,is the length ofa shortest(u,v) -pathin G.The diameter of a connected graph G is the maximum distance between two verticesof G.For X V(G) ,the neighbor set NG(X) of X is defined byNG(X) ={ y∈V(G) \X:there is x∈X such thatxy∈E(G) } .NG({ x} )…
|
| 收稿时间： | 17 March 2003 |
PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS |
| |
| Yang Aifeng , Yuan Jinjiang Dept. of Appl. Math.,South China Univ. of Tech.,Guangdong ,China. Dept. of Math.,Zhengzhou Univ.,Henan ,China..PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS[J].Applied Mathematics A Journal of Chinese Universities,2004,19(3):245-251. |
| |
| Authors: | Yang Aifeng Yuan Jinjiang Dept of Appl Math South China Univ of Tech Guangdong China Dept of Math Zhengzhou Univ Henan China |
| |
| Institution: | (1) Dept. of Appl. Math., South China Univ. of Tech., 510640 Guangdong, China;(2) Dept. of Math., Zhengzhou Univ., 450052 Henan, China |
| |
| Abstract: | 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), GV
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 (10371112) and the Natural Science Foundation of Henan (0411011200). |
| |
| Keywords: | induced matching partition coloring |
| 本文献已被 CNKI SpringerLink 等数据库收录！ |
