Some Results On Independent Cycles And Independent Cliques In Graphs

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 dG(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 is the minimum degree sum of nonadjacent vertices. (When G is a complete graph, we define (σ2(G)=∞).For a bipartite graph G with partite sets V1 and V2, define(When G is a complete bipartite graph, we defineσ1,1=∞). When｜Vi｜=｜V2｜, we call G a balance bipartite graph.The complete bipartite graph K1,3 is called a claw, and G is said to be claw-free if G has no induced subgraph isomorphic to K1,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 independent cycles,2-factor and path-factor theory in G are important problems in graph factorial theory, also they are the extending of Hamilton cycle theory. The discussion is mature and perfect increasingly. And it is important applications to computer science and network. The study of independent cycles, 2-factor and path-factor theory mostly focus on following:Graph containing spec-ified number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length, graph containing independent cycles and 2-factor which have specified properties, and path-factor which have specified properties, etc.The innovation of this paper is discussing the graph containing specified number of independent 3-cliques and 4-cliques. The paper is divided into four chapters. In Chapter 1, we introduce some basic notations and give a concise survey on the history and the progress on the cycle theory, and some primary results about the paper. This chapter is the base of the next three chapters.In Chapter 2, we investigate the graph containing independent cycles which have specified properties and prove the following result.Theorem2.1.1 Let s and k be two positive integers with s(?)k and let G be a graph of order n. Ifn(?)3s+4(k-s)+7, then G has a 2-factor with k+1 cycles C1...Ck+1 such that l(Ci)= 3 for 1(?)i(?)s-1, l(Ci)=4 for s(?)i(?)k-3, l(Ci)< 4 for k-2(?)i(?)k-1 and l(Ck)∈{3,4,7,8}.In Chapter 3, we investigate the graph containing specified length of inde-pendent cliques. In this chapter, we have the following result.Theorem3.1.1 Let s and k be two integers with 0(?)s(?)k and let G be a graph of order n. If n(?)3s+4(K-s) andσ2(G)(?)3(n-s)/2+k-1, then G contains s disjoint 3-cliques and k-s disjoint 4-cliques such that all of them are disjoint, i.e., G(?)sK3+(k-s)K4.In Chapter 4,we investigate the claw-free graph containing independent cliques which have specified properties and prove the following result.Theorem4.1.1 Suppose G is a non-empty claw-free graph. Let s and k be two integers with 0(?)s(?)k. If n(?)3s+4(k-s) andβ(G)> 3(n-s-1)/2, then G contains s disjoint 3-cliques and k-s disjoint 4-cliques such that all of them are disjoint, i.e., G(?)sK3+(k-s)K4. Furthermore, In Chapter 3 and Chapter 4, we list some problems for future research.