2-边连通图的线图的P_3因子(英文)

P_3-factors in the Line Graphs of 2-edge-connected Graphs

下载PDF

导出

摘要如果图G有一个生成子图使得这个生成子图的每一个分支都是3个点的路,则称G有P_3-因子.本文证明了对任何一个2-边连通图G,只要G的边数能被3整除,则G的线图就有P_3-因子。 A graph G has a P3-factor if G has a spanning subgraph each component of which is a path on three vertices. In this paper we show that the line graph of any 2-edge-connected graph whose size is divisible by 3 has a P3-factor

作者刘清海张昭

机构地区新疆大学数学与系统科学学院

出处《数学研究》 CSCD 2008年第3期251-255,共5页 Journal of Mathematical Study

基金 supported by NSFC(60603003) the Key Project of Chinese Ministry of Education(208161) and XJEDU

关键词 P3-因子线图 P3-factor line graph

分类号 O157.5 [理学—基础数学]

引文网络
相关文献

参考文献12

1Hell P and Kirkpatrick D G. On the completeness of a generalized matching problem. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, San Diego, 1978: 240-245.
2Hell P and Kirkpatrick D G. On the complexity of general graph factor problems. SIAM J. Comp., 1983, 12: 601-609.
3Li X J and Zhang Z. Path-factor in line graphs of trees, to appear in Chnese Quarterly Journal of Mathmatic.
4Akiyama J and Kano M. Factors and factorizations of graphs - a survey. J. Graph Theory, 1985, 9: 1-42.
5Ando K, Egawa Y, Kaneko A et al. Path factors in claw-free graphs. Discrete Math., 2002, 243: 195-200.
6Ishizuka S. Closure, path-factors and path coverings in claw-free graphs. Ars Combin., 1998, 50: 115-128.
7Johansson R. An E1-Zahar type condition ensuring path-factors. J. Graph Theory, 1998, 28: 39-42.
8Kaneko A. A necessary and sufficent condition for the existence of a path factor every component of which is a path of length at least two. J. Combin. Theory Set. B, 2003, 88: 195-218.
9Kano M, Katona G Y and Kiraly Z. Packing paths of length at least two. Discrete Math., 2004, 283: 129-135.
10Kawarabayashi K, Matsuda H, Oda Yet al. Path factors in cubic graphs. J. Graph Theory, 2002, 39: 188-193.

1华瑛,王晓.一个关于树图的P_3-因子存在性的充要条件[J].商洛学院学报,2009,23(2):23-25.
2施静,郭畅.完全多重图λK_ν的{p_2~*,p_3}-因子分解[J].南通大学学报（自然科学版）,2015,14(2):61-63.

数学研究

2008年第3期

浏览历史

内容加载中请稍等...

2-边连通图的线图的P_3因子(英文)

参考文献12

相关作者

相关机构

相关主题

浏览历史