| 图中相互独立的4圈和含4个点的路 |
| |
| 引用本文： | 颜谨,刘桂真.图中相互独立的4圈和含4个点的路[J].数学物理学报(A辑),2003,23(6):711-718. |
| |
| 作者姓名： | 颜谨 刘桂真 |
| |
| 作者单位： | 山东大学数学与系统科学学院 济南250100
(颜谨)，山东大学数学与系统科学学院 济南250100(刘桂真) |
| |
| 基金项目： | 国家自然科学基金 ( 6 0 172 0 0 3)，山东省自然科学基金( Z2 0 0 0 A 0 2 )资助项目 |
| |
| 摘 要： | 设k是一个正整数，G是一个顶点数为|G|=4k的图. 假设σ\-2(G)≥4k-1, 则G有一个支撑子图含k-1个4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的. 设G=(V\-1,V \-2;E)是一个二分图使得|V\-1|=|V\-2|=2k. 如果对G中每一对满足x∈V\-1和y∈V\-2的不 相邻的顶点x和y 都有d(x)+d(y)≥2k+1, 则G包含k-1个相互独立的4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的，并且此度条件是最好的.
|
| 关 键 词： | 图 最小度 圈. |
| 文章编号： | 1003-3998(2003)06-711-08 |
Quadrilaterals and Paths of Order 4 in Graphs |
| |
| YAN Jin,LIU Gui-Zhen.Quadrilaterals and Paths of Order 4 in Graphs[J].Acta Mathematica Scientia,2003,23(6):711-718. |
| |
| Authors: | YAN Jin LIU Gui-Zhen |
| |
| Abstract: | Let k be a positive integer. Let G be a graph with |G|=4k. Supposeing σ\-2(G)≥4k-1, then G has a spanning subgra ph consisting of k-1quadrilaterals and a path of order 4 such that all of them are independent. Let G=(V\-1,V\-2;E) be a bipartite graph with |V\-1|=|V\-2|=2 k. If d(x)+d(y)≥2k+1 for each pair of nonadjacent vertices x and y of G with x∈V\-1and y∈V\-2, then G contains k-1 quadri laterals and a path of order 4 such that all of them are independent. Moreover,the condition on degrees is sharp. |
| |
| Keywords: | Graph Minimum degree Cycle |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《数学物理学报(A辑)》浏览原始摘要信息 |
| 点击此处可从《数学物理学报(A辑)》下载免费的PDF全文 |
