图中相互独立的4圈和含4个点的路

数学物理学报 ›› 2003, Vol. 23 ›› Issue (6): 711-718.

图中相互独立的4圈和含4个点的路

颜谨, 刘桂真

山东大学数学与系统科学学院济南 250100

出版日期:2003-12-25 发布日期:2003-12-25
基金资助:
国家自然科学基金（60172003）和山东省自然科学基金（Z2000A02)资助项目

Quadrilaterals and Paths of Order 4 in Graphs

YAN Jin, LIU Gui-Zhen

山东大学数学与系统科学学院济南 250100

Online:2003-12-25 Published:2003-12-25
Supported by:
国家自然科学基金（60172003）和山东省自然科学基金（Z2000A02)资助项目

摘要/Abstract

摘要：

设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的路，使得所有这些圈和路都是相互独立的，并且此度条件是最好的.

关键词: 图；最小度；圈.

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.

Key words: Graph, Minimum degree, Cycle

中图分类号:

05C38，05C70

颜谨, 刘桂真. 图中相互独立的4圈和含4个点的路[J]. 数学物理学报, 2003, 23(6): 711-718.

YAN Jin, LIU Gui-Zhen. Quadrilaterals and Paths of Order 4 in Graphs[J]. Acta mathematica scientia,Series A, 2003, 23(6): 711-718.