系列平行图的除V*外的边覆盖划分被引量：1

导出

摘要任意给定系列平行图G的一个顶点v^＊,则G的边集可划分为k=min{k′（G）＋1，δ（G）}个子集，使得每一个边子集覆盖可能除v^＊以外的所有顶点，其中δ（G）为G的最小度，k′（G）为G的边连通度．另外，证明了该结果是最好的可能，并且通过此证明过程得到一个可找到该划分的多项式时间算法．

作者刘桂真邓小铁徐常青

机构地区山东大学数学与系统科学学院香港城市大学计算机系河北工业大学应用数学系

出处《中国科学（A辑）》 CSCD 北大核心 2006年第6期659-668,共10页 Science in China(Series A)

基金国家自然科学基金(批准号:10471078) 高校博士点基金(批准号:20040422004) 香港研究基金(批准号:CityU 1056/01E)资助项目

关键词系列平行图边连通度边覆盖染色极大-极小定理

参考文献1

1MIAOLianying,LIUGuizhen.EDGE COVERING COLORING AND FRACTIONAL EDGE COVERING COLORING[J].Journal of Systems Science & Complexity,2002,15(2):187-193. 被引量：10

1R.P. Gupta, Studies in the Theory of Graphs, Thesis, Tata Inst. Fund. Res., Bombay, 1967.
2D. de Werra, A sufficient condition for equitable edge-coloring of simple graphs, Descrete Math.,1994, 128: 179-201.
3R. Edward, Scheinerman and Daniel, Fractional Graph Theory, Johnwiley and Sons, Inc. New York, 1997.
4J. A. Bondy and R.U.S., Graph Theory with Applications, Elsevier, New York, 1976.
5S. Fiorini and R. J. Wilson, Edge-colorings of graphs, Research Notes in Mathematics, 1977, Vol. 16.

1LIU Guizhen, DENG Xiaotie & XU Changqing School of Mathematics and System Science, Shandong University, Jinan 250100, China,Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, China,Department of Applied Mathematics, Hebei University of Technology, Tianjin 300130, China.Partitioning series-parallel multigraphs into υ*-excluding edge covers[J].Science China Mathematics,2006,49(8):1082-1093.
2宋慧敏,刘桂真.ON f-EDGE COVER-COLOURING OF SIMPLE GRAPHS[J].Acta Mathematica Scientia,2005,25(1):145-151. 被引量：1
3王纪辉,刘桂真.图的边覆盖染色与分数边覆盖染色[J].山东大学学报（理学版）,2005,40(3):1-4. 被引量：6
4王纪辉.关于近似二部图边覆盖染色的一个充分条件[J].山东大学学报（理学版）,2006,41(1):21-23. 被引量：1
5韩淑芹,高洪国.几类图的全色极大团染色[J].山东科学,2007,20(1):1-2. 被引量：1
6JIA YAN-BIN,Xu CHANG-QING.On f-edge Cover Chromatic Index of Multigraphs[J].Communications in Mathematical Research,2009,25(5):429-432.
7韩淑芹.若干图类的全色极大团色数[J].鲁东大学学报（自然科学版）,2015,31(3):214-216.
8陈琴.边覆盖染色问题的有效算法[J].中国科学：数学,2016,46(3):351-370. 被引量：1
9韩淑芹.一类新的染色问题[J].山东理工大学学报（自然科学版）,2014,28(3):50-51.

中国科学（A辑）

2006年第6期

内容加载中请稍等...