The Vertex-disjoint Triangles And Quadrilaterals Problem In The Special Graph

Almost two decades have passed since the appearance of those graph theory texts that still set the agenda for most introductory courses taught today. The canon created by those books has helped to identify some main fields of study and research, and will doubtless continue to influence the development of the discipline for some time to come. Yet much has happened in those 20 years, in graph theory no less than elsewhere:deep new theorems have been found, seemingly disparate methods and results have become interrelated, entire new branches have arisen. To name just a few such developments, one may think of the following problems.All graphs considered in this paper are finite, simple and undirected graphs. For a graph G, we denote by V(G), E(G), F(G),6(G) and△(G) the vertex set, the edge set, the face set, the minimum(vertex) degree and the maximum(vertex) degree of G. A set of subgraphs of G is said to be vertex-disjoint or independent if no two of them have any common vertex in G, and we use disjoint to stand for vertex-disjoint throughout this paper. We call a cycle of length 3 a triangle and a cycle of length 4 a quadrilateral.vertex-disjoint triangles(VDT) problem asks for a set of maximum number of pairwise vertex-disjoint triangles in a given graph G.The triangle cover problem asks for the existence of a perfect triangle packing in a graph G. The other problem considers about a quadrilaterals in a graph G. The focus of this paper is just to consider the vertex-disjoint triangles and quadrilaterals problem in a special graph G. A graph is said to beΚ1,t-free if it does not contain an induced subgraph isomorphic to K1,t.In this paper, by constructing aΚ1,4-free graph of order 9(κ-1) and with minimum degree four, we disprove the conjecture raised by Hong Wang (Combinatorica 18(1998),441-447). At the same time, we prove that for any positive integer k, if G is aΚ1,4-free graph of order at least 9(κ-1) +1 andδ(G)> 4, then G contains k vertex-disjoint triangles. Furthermore, this bound is sharp.Recently, Wang [12] gave a further result about quadrilaterals, which states that if G is a graph of order n with 4κ+1 2k+1, then G contains k disjoint quadrilaterals. In that paper, he has not found examples to show the sharpness of the condition for n=4κ+2, he propose some conjecture. We consider the conjectures, we prove theorem:Letκ> 2 be a posotive integer and G a graph of order 4κ+2. If the minimum degree of G is at least 2κ. Then G contains k independent quadrilaterals or G= (k-1)C4∪P5∩χ0, e(P5,χ0)= 0.