关于图中相互独立的圈和2-因子的新结果
|
摘要
本文考虑的图若无特殊声明均为简单、无向有限图，对于一个图G=G(V(G)，E(G))，我们用V(G)和E(G)分别表示图的顶点集合和边集合．对任意的v∈V(G)，我们用d_G(v)表示顶点v在G中的度数．△(G)和δ(G)分别表示图G的最大度和最小度，在不引起混淆的情况下简记为△和δ。对于图G，我们用|G|=|V(G)|表示G的阶数，即G的顶点数，并定义图G中两个不相邻的顶点的最小度和为：σ_2(G) = min{d_G(x)+d_G(y)|x,y∈V(G),x≠y,xy (?) E(G)}
(若G是一个完全图，则令σ_2(G)=∞)．
对图G中任意点u，u的邻域定义如下：N_G(u) = {x∈V(G)|xu∈E(G)}．
完全二部图K_(1,3)称为一个爪，如果G不含同构于K_(1，3)的生成子图，则称G是无爪图．对于图G中的一条路P和一个圈C，定义路和圈的长度分别为：l(P) = |V(P)| - 1, l(C) = |V(C)|．
G的一个哈密顿圈是G的包含G中所有顶点的一个圈．G的一个1-因子是G的一个1-正则支撑子图，通常我们称1-因子为完美对集或完美匹配．显然G的一个1-因子是覆盖G的所有顶点的一个边集合。G的一个2-因子是G的一个2-正则支撑子图，易见2-因子的每一个连通分支为一个圈．图的k个独立圈是指G中k个顶点不相交的圈．
图的独立圈、2-因子问题是图的因子理论中非常重要的一部分，也是图的哈密顿圈理论的推广和延伸．它是图论中非常有趣的一类问题，其理论研究日益成熟和完善，而且它在计算机科学、通信网络设计等中都有重要应用。关于图的独立圈、2-因子的研究主要集中在以下几个方面：图中含指定个数的独立圈和2-因子，含指定长度的独立圈和2-因子和图中具有指定性质的独立圈和2-因子等等。
全文共分三章。第一章简单介绍了图论的基本概念，圈和因子的历史和发展状况及一些已有的相关结论。这一章是第二章和第三章的基础．
在本文的第二章中，我们研究了图中含指定长度的相互独立的圈问题，颜谨[17]证明了下面的的结论：如果G是一个简单图，s，k是两个正整数并且s≤k，其中G的顶点个数n≥3s+4(k-s)+3．如果σ_2(G)≥n+s，那么G包含k个顶点不相交的圈C_1,…，C_k并且|C_i|=3其中1≤i≤s，|C_i|=4其中s 定理2．1．1．如果G是一个简单图，s，k是两个正整数并且s≤k，其中G的顶点个数n≥3s+4(k-s)+3。如果σ_2(G)≥n+2k-s+3/2，那么G包含k个顶点不相交的圈C_1，…，C_k并且|C_i|=3其中1≤i≤s，|C_i|=4，|E(C_i)|≥5其中s 第三章我们则讨论了图中含指定边和指定长度的图的2-因子的问题．其主要结果如下：
定理3．1．1．设G是一个有n_1+n_2+1个顶点的简单图，其中n_1≥3，n_2≥3．若δ(G)≥(?)3n_1/4(?)+(?)3n_2/4(?)+1，那么G包含两个顶点不相交的圈C_1，C_2，其中|C_1|=n_i+1，|C_2|=n_j(i，j=1，2)，并且(?)e∈G我们有e∈E(C_1)或e∈E(C_2)。
All graphs considered in this paper are finite simple graphs. Let G = (V(G), E(G)) be a graph, where V(G) and E(G) denote the vertex set and edge set of G, respectively. We use d_G(v) to stand for the degree of v in G. Let△(G) andδ(G) denote the maximum and the minimum vertex degree of G, respectively. For a graph G, |G| = |V(G)| is the order of G, andσ_2(G) = min{d_G(x)+d_G(y)|x,y∈V(G),x≠y,xy (?) E(G)}is the minimum degree sum of nonadjacent vertices. (When G is a complete graph, we defineσ_2(G) =∞).
For a vertex u of G, the neighborhood of u are denoted by N_G(u) = {x∈V(G)|xu∈E(G)} .The complete bipartite graph K_(1,3) is called a claw, and G is said to be claw-free if G has no induced subgraph isomorphic to K_(1,3). Let P be a path and C a cycle. We denote the length of P and the length of C by l(P) and l(C), respectively. That is, l(P) = |V(P)| - 1, l(C) = |V(C)|.
A Hamilton cycle of G is a cycle of G which contains every vertex of G. A 1-factor of a graph G is a 1-regular spanning subgraph of G, and we call a 1-factor a perfect matching. It is readily seen that a 1-factor of G is a collection of independent edges that covers all vertices of G. A 2-factor of G is a 2-regular spanning subgraph of G. Clearly, each component of a 2-factor of G is a cycle, k independent cycles of G are k cycles which have no common vertex.
The theory of independent cycles and 2-factor of graphs is the extending of Hamilton cycle theory. It is an interesting problem in graph theory. Furthermoreit has important applications to computer science and networks. The study of independent cycles and 2-factor theory mostly focuses on the following: Aspects graph containing specified number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length,and Graph containing independent cycles and 2-factor which have specified properties, etc.
The paper is divided into three chapters. In Chapter 1, we introduce some basic notations, the history of the cycle theory . This chapter is the base of the next two chapters.
Concerning independent cycles containing specified length, Yan Jin[17] proved the next result . Let s and k be two positive integers with s≤k, and let G be a graph of order n≥3s + 4(k - s) + 3. Ifσ_2(G)≥n + s, then G contains k disjoint cycles C_1,…,C_k satisfying |C_i| = 3 for 1≤i≤s and |C_i| = 4 for s < i≤k. In Chapter 2, we have the following result.
Theorem2.1.1. Let s and k be two positive integers with s≤k, and let Gbe a graph of order n≥3s + i(k - s) + 3. Ifσ_2(G)≥n + 2k - s+3/2, then G contains k disjoint cycles C_1 ,…,C_k satisfying |C_i| = 3 for 1≤i≤s and |C_i| = 4, |E(C_i)|≥5 for s In Chapter 3, we investigate the graph containing independent cycles which have specified edges. In this chapter, the main result is as the following theorem.
Theorem3.1.1. Let G be a simple graph of order n_1+n_2 + 1, and n_1≥3,n_2≥3.Ifδ(G)≥(?)3n_1/4(?)+(?)3n_2/4(?)+ 1, then G contains two disjoint cycles C_1, C_2 satisfying |C_1| =n_i + 1, |C_2| = n_j(i,j = 1,2), and (?)e∈G we have e∈E(C_1) or e∈E(C_2).
(若G是一个完全图，则令σ_2(G)=∞)．
对图G中任意点u，u的邻域定义如下：N_G(u) = {x∈V(G)|xu∈E(G)}．
完全二部图K_(1,3)称为一个爪，如果G不含同构于K_(1，3)的生成子图，则称G是无爪图．对于图G中的一条路P和一个圈C，定义路和圈的长度分别为：l(P) = |V(P)| - 1, l(C) = |V(C)|．
G的一个哈密顿圈是G的包含G中所有顶点的一个圈．G的一个1-因子是G的一个1-正则支撑子图，通常我们称1-因子为完美对集或完美匹配．显然G的一个1-因子是覆盖G的所有顶点的一个边集合。G的一个2-因子是G的一个2-正则支撑子图，易见2-因子的每一个连通分支为一个圈．图的k个独立圈是指G中k个顶点不相交的圈．
图的独立圈、2-因子问题是图的因子理论中非常重要的一部分，也是图的哈密顿圈理论的推广和延伸．它是图论中非常有趣的一类问题，其理论研究日益成熟和完善，而且它在计算机科学、通信网络设计等中都有重要应用。关于图的独立圈、2-因子的研究主要集中在以下几个方面：图中含指定个数的独立圈和2-因子，含指定长度的独立圈和2-因子和图中具有指定性质的独立圈和2-因子等等。
全文共分三章。第一章简单介绍了图论的基本概念，圈和因子的历史和发展状况及一些已有的相关结论。这一章是第二章和第三章的基础．
在本文的第二章中，我们研究了图中含指定长度的相互独立的圈问题，颜谨[17]证明了下面的的结论：如果G是一个简单图，s，k是两个正整数并且s≤k，其中G的顶点个数n≥3s+4(k-s)+3．如果σ_2(G)≥n+s，那么G包含k个顶点不相交的圈C_1,…，C_k并且|C_i|=3其中1≤i≤s，|C_i|=4其中s
定理3．1．1．设G是一个有n_1+n_2+1个顶点的简单图，其中n_1≥3，n_2≥3．若δ(G)≥(?)3n_1/4(?)+(?)3n_2/4(?)+1，那么G包含两个顶点不相交的圈C_1，C_2，其中|C_1|=n_i+1，|C_2|=n_j(i，j=1，2)，并且(?)e∈G我们有e∈E(C_1)或e∈E(C_2)。
All graphs considered in this paper are finite simple graphs. Let G = (V(G), E(G)) be a graph, where V(G) and E(G) denote the vertex set and edge set of G, respectively. We use d_G(v) to stand for the degree of v in G. Let△(G) andδ(G) denote the maximum and the minimum vertex degree of G, respectively. For a graph G, |G| = |V(G)| is the order of G, andσ_2(G) = min{d_G(x)+d_G(y)|x,y∈V(G),x≠y,xy (?) E(G)}is the minimum degree sum of nonadjacent vertices. (When G is a complete graph, we defineσ_2(G) =∞).
For a vertex u of G, the neighborhood of u are denoted by N_G(u) = {x∈V(G)|xu∈E(G)} .The complete bipartite graph K_(1,3) is called a claw, and G is said to be claw-free if G has no induced subgraph isomorphic to K_(1,3). Let P be a path and C a cycle. We denote the length of P and the length of C by l(P) and l(C), respectively. That is, l(P) = |V(P)| - 1, l(C) = |V(C)|.
A Hamilton cycle of G is a cycle of G which contains every vertex of G. A 1-factor of a graph G is a 1-regular spanning subgraph of G, and we call a 1-factor a perfect matching. It is readily seen that a 1-factor of G is a collection of independent edges that covers all vertices of G. A 2-factor of G is a 2-regular spanning subgraph of G. Clearly, each component of a 2-factor of G is a cycle, k independent cycles of G are k cycles which have no common vertex.
The theory of independent cycles and 2-factor of graphs is the extending of Hamilton cycle theory. It is an interesting problem in graph theory. Furthermoreit has important applications to computer science and networks. The study of independent cycles and 2-factor theory mostly focuses on the following: Aspects graph containing specified number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length,and Graph containing independent cycles and 2-factor which have specified properties, etc.
The paper is divided into three chapters. In Chapter 1, we introduce some basic notations, the history of the cycle theory . This chapter is the base of the next two chapters.
Concerning independent cycles containing specified length, Yan Jin[17] proved the next result . Let s and k be two positive integers with s≤k, and let G be a graph of order n≥3s + 4(k - s) + 3. Ifσ_2(G)≥n + s, then G contains k disjoint cycles C_1,…,C_k satisfying |C_i| = 3 for 1≤i≤s and |C_i| = 4 for s < i≤k. In Chapter 2, we have the following result.
Theorem2.1.1. Let s and k be two positive integers with s≤k, and let Gbe a graph of order n≥3s + i(k - s) + 3. Ifσ_2(G)≥n + 2k - s+3/2, then G contains k disjoint cycles C_1 ,…,C_k satisfying |C_i| = 3 for 1≤i≤s and |C_i| = 4, |E(C_i)|≥5 for s
Theorem3.1.1. Let G be a simple graph of order n_1+n_2 + 1, and n_1≥3,n_2≥3.Ifδ(G)≥(?)3n_1/4(?)+(?)3n_2/4(?)+ 1, then G contains two disjoint cycles C_1, C_2 satisfying |C_1| =n_i + 1, |C_2| = n_j(i,j = 1,2), and (?)e∈G we have e∈E(C_1) or e∈E(C_2).
引文
[1] J. A. Bondy and U . S. R. Murty, Graph Theory with Applications, MacMillan, London, (1976).
[2] G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (3) (1952) 69-81.
[3] O. Ore. Note on hamiltonian circuits. Amer. Math. Monthly. 67 (1960) 55.
[4] J. Moon, L. Moser, On hanmiltonian bipartite graphs. Israel J. Math. 1 (1963) 163-165.
[5] K. Corrddi, A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar. 14 (1963) 423-439.
[6] P. Justesen, On independent circuits in finite graphs and conjecture of Erdos and Posa, Ann. Discrete Math. 41 (1989) 299-306.
[7] H. Enomoto, On the existence of disjoint cycles in a graph. Combinatorica. 18 (1998) 487-492.
[8] H. Wang, On the maximum number of independent cycles in a graph. Discrete Math. 205 (1999) 183-190.
[9] S. Brandt, G. Chen, R. Faudree, R. J. Gould, L. Lesniak, Degree conditions for 2-factors. J. Graph Theory. 24 (1997) 165-173.
[10] M. H. El-Zahar, On circuits in graphs. Discrete Math. 50 (1984) 227-230.
[11] P. Catlin, Embedding subgraphs and coloring graphs under extremal conditions. Ph. D. Dissertation. Ohio State University. (1976).
[12] M. Aiger, S. Brandt, Embedding arbitrary graphs of maximum degree two. J. London Math. Soc. (2) 48 (1993) 39-51.
[13] H. Wang, Covering a graph with cycles. J. Graph Theory. 20 (1995) 203-211.
[14] H. Enomoto, Graph partition problems into cycles and paths. Discrete Math. 233 (2001) 93-101.
[15] H. Wang, Two vertex-disjoint cycles in a graph. Graphs Combin. 11 (4) (1995) 389-396.
[16] G. A. Dirac, On the maximal number of independent triangles. Abh. Math. Semin. Univ. Hamb. 26 (1963) 78-82.
[17] J.Yan, Disjoint triangles and quadrilaterals in a graph. Discrete Math. Article in Press
[18] H. Wang, On quadriltaterals and cycles covers in a bipartite graph. Ars Combin. 58 (2001) 301-311.
[19] H. Wang, Vertex-disjoint hexagons with chords in a bipartite graph. Discrete Math. 187 (1998) 221-231.
[20] D. Amar, Partition of a bipartite hamiltonian graph into two cycles. Discrete Math. 58 (1986) 1-10.
[21] H. Wang, Partition of a bipartite graph into cycles. Discrete Math. 117 (1993) 287-291.
[22] H. Wang, Bipartite graphs containing every possible pair of cycles. Discrete Math. 207 (1999) 233-242.
[23] H. Wang, Covering a graph with cycles passing through given edges. J. Graph Theory. 26 (1997) 105-109.
[24] Y. Egawa, R. J. Fraudree, E. Gyori, Y. Ishigami, R. H. Schelp, H. Wang, Vertexdisjointcycles containing specified edges. Graphs and Combinatorics. 16 (2000) 81-92.
[25] H. Wang,Proof of a conjecture on cycles in a bipartite graph. J. Graph Theory. 31 (1999) 333-343.
[26] J.Yan, G.Z.Liu, on 2-factors with cycles containing specified edges in a bipartite graph. Discrete Math. 207 (1999) 233-242.
[27] J.Yan, G.Z.Liu, on 2-factors with prescribed properties in a bipartite graph. Acta Mathematica Sinica. 22 (2006) 1115-1120.
[28] J.Yan, G.Z.Liu, on 2-factors with quadrilaterals containing specified vertices of a bipartitegraph. Ars. Combin. 82 (2007) 133-144.
[29] J.Yan, G.Z.Liu, Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph. J. Application and Math. Computing.
[30]耿建艳，图的劝和路因子理论的若干结果及对平面图中全染色猜想的研究。山东大 学硕士论文。2007年。
[31] H. Wang, On Vertex -Disjoint Complete Bipartite Subgraphs in a Bipartite Graph. Graphs and Combinatorics. 15 (1999) 353-364.
[32] H. Wang, On the maximum number of independent cycles in a bipartite graph. J. Combin. Theory Ser. B 67 (1996) 152-164.
[33]颜谨，图的独立圈和k-因子。山东大学博士论文。2003年。
[2] G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (3) (1952) 69-81.
[3] O. Ore. Note on hamiltonian circuits. Amer. Math. Monthly. 67 (1960) 55.
[4] J. Moon, L. Moser, On hanmiltonian bipartite graphs. Israel J. Math. 1 (1963) 163-165.
[5] K. Corrddi, A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar. 14 (1963) 423-439.
[6] P. Justesen, On independent circuits in finite graphs and conjecture of Erdos and Posa, Ann. Discrete Math. 41 (1989) 299-306.
[7] H. Enomoto, On the existence of disjoint cycles in a graph. Combinatorica. 18 (1998) 487-492.
[8] H. Wang, On the maximum number of independent cycles in a graph. Discrete Math. 205 (1999) 183-190.
[9] S. Brandt, G. Chen, R. Faudree, R. J. Gould, L. Lesniak, Degree conditions for 2-factors. J. Graph Theory. 24 (1997) 165-173.
[10] M. H. El-Zahar, On circuits in graphs. Discrete Math. 50 (1984) 227-230.
[11] P. Catlin, Embedding subgraphs and coloring graphs under extremal conditions. Ph. D. Dissertation. Ohio State University. (1976).
[12] M. Aiger, S. Brandt, Embedding arbitrary graphs of maximum degree two. J. London Math. Soc. (2) 48 (1993) 39-51.
[13] H. Wang, Covering a graph with cycles. J. Graph Theory. 20 (1995) 203-211.
[14] H. Enomoto, Graph partition problems into cycles and paths. Discrete Math. 233 (2001) 93-101.
[15] H. Wang, Two vertex-disjoint cycles in a graph. Graphs Combin. 11 (4) (1995) 389-396.
[16] G. A. Dirac, On the maximal number of independent triangles. Abh. Math. Semin. Univ. Hamb. 26 (1963) 78-82.
[17] J.Yan, Disjoint triangles and quadrilaterals in a graph. Discrete Math. Article in Press
[18] H. Wang, On quadriltaterals and cycles covers in a bipartite graph. Ars Combin. 58 (2001) 301-311.
[19] H. Wang, Vertex-disjoint hexagons with chords in a bipartite graph. Discrete Math. 187 (1998) 221-231.
[20] D. Amar, Partition of a bipartite hamiltonian graph into two cycles. Discrete Math. 58 (1986) 1-10.
[21] H. Wang, Partition of a bipartite graph into cycles. Discrete Math. 117 (1993) 287-291.
[22] H. Wang, Bipartite graphs containing every possible pair of cycles. Discrete Math. 207 (1999) 233-242.
[23] H. Wang, Covering a graph with cycles passing through given edges. J. Graph Theory. 26 (1997) 105-109.
[24] Y. Egawa, R. J. Fraudree, E. Gyori, Y. Ishigami, R. H. Schelp, H. Wang, Vertexdisjointcycles containing specified edges. Graphs and Combinatorics. 16 (2000) 81-92.
[25] H. Wang,Proof of a conjecture on cycles in a bipartite graph. J. Graph Theory. 31 (1999) 333-343.
[26] J.Yan, G.Z.Liu, on 2-factors with cycles containing specified edges in a bipartite graph. Discrete Math. 207 (1999) 233-242.
[27] J.Yan, G.Z.Liu, on 2-factors with prescribed properties in a bipartite graph. Acta Mathematica Sinica. 22 (2006) 1115-1120.
[28] J.Yan, G.Z.Liu, on 2-factors with quadrilaterals containing specified vertices of a bipartitegraph. Ars. Combin. 82 (2007) 133-144.
[29] J.Yan, G.Z.Liu, Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph. J. Application and Math. Computing.
[30]耿建艳，图的劝和路因子理论的若干结果及对平面图中全染色猜想的研究。山东大 学硕士论文。2007年。
[31] H. Wang, On Vertex -Disjoint Complete Bipartite Subgraphs in a Bipartite Graph. Graphs and Combinatorics. 15 (1999) 353-364.
[32] H. Wang, On the maximum number of independent cycles in a bipartite graph. J. Combin. Theory Ser. B 67 (1996) 152-164.
[33]颜谨，图的独立圈和k-因子。山东大学博士论文。2003年。
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |