【作者】 于潇；

【导师】 颜谨；

【作者基本信息】 山东大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 本文考虑的图若无特殊声明均为简单、无向有限图，对于一个图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中两个不相邻的顶点的最小度和为：σ₂（G） = min{d_G（x）+d_G（y）|x,y∈V（G）,x≠y,xy （?） E（G）}（若G是一个完全图，则令σ₂（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．如果σ₂（G）≥n+s，那么G包含k个顶点不相交的圈C₁,…，C_k并且|C_i|=3其中1≤i≤s，|C_i|=4其中s<i≤k。在第二章中我们则有以下结论：定理2．1．1．如果G是一个简单图，s，k是两个正整数并且s≤k，其中G的顶点个数n≥3s+4（k-s）+3。如果σ₂（G）≥n+2k-s+3/2，那么G包含k个顶点不相交的圈C₁，…，C_k并且|C_i|=3其中1≤i≤s，|C_i|=4，|E（C_i）|≥5其中s<i≤后．第三章我们则讨论了图中含指定边和指定长度的图的2-因子的问题．其主要结果如下：定理3．1．1．设G是一个有n₁+n₂+1个顶点的简单图，其中n₁≥3，n₂≥3．若δ（G）≥（?）3n₁/4（?）+（?）3n₂/4（?）+1，那么G包含两个顶点不相交的圈C₁，C₂，其中|C₁|=n_i+1，|C₂|=n_j（i，j=1，2），并且（?）e∈G我们有e∈E（C₁）或e∈E（C₂）。更多还原

【Abstract】 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σ₂（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σ₂（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σ₂（G）≥n + s, then G contains k disjoint cycles C₁,…,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σ₂（G）≥n + 2k - s+3/2, then G contains k disjoint cycles C₁ ,…,C_k satisfying |C_i| = 3 for 1≤i≤s and |C_i| = 4, |E（C_i）|≥5 for s<i≤k.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₁+n₂ + 1, and n₁≥3,n₂≥3.Ifδ（G）≥（?）3n₁/4（?）+（?）3n₂/4（?）+ 1, then G contains two disjoint cycles C₁, C₂ satisfying |C₁| =n_i + 1, |C₂| = n_j（i,j = 1,2）, and （?）e∈G we have e∈E（C₁） or e∈E（C₂）.更多还原