Vertex-disjoint K_1+(K_1 ∪ K_2) in K_(1,4)-free Graphs with Minimum Degree at Least Four

A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4.Let k be an integer with k≥2.We prove that ifG is a K1,4-free graph of order at least 11k-10 with minimum degree at least four,then G contains k vertex-disjoint copies of K1+(K1∪K2).     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

A degree condition for the existence of regular factors in K1, n-free graphs

A graph is called K_{1, n}-free if it contains no K_{1, n} as an induced subgraph. Let n(≥3), r be integers (if r is odd, r ≥ n − 1). We prove that every K_{1, n}-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least. $ \left(n+{{n-1}\over{r}}\right) \left\lceil {n\over{2(n-1)}}r \right\rceil - {{n-1}\over{r}}\left(\left\lceil {n\over{2(n-1)}}r \right\rceil \right)^2+n-3. $ This degree condition is sharp. © 1996 John Wiley & Sons, Inc.     

Matching Properties in Total Domination Vertex Critical Graphs

A vertex subset S of a graph G = (V,E) is a total dominating set if every vertex of G is adjacent to some vertex in S. The total domination number of G, denoted by γ _t (G), is the minimum cardinality of a total dominating set of G. A graph G with no isolated vertex is said to be total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ _t (G?v) < γ _t (G). A total domination vertex critical graph G is called k-γ _t -critical if γ _t (G) = k. In this paper we first show that every 3-γ _t -critical graph G of even order has a perfect matching if it is K _1,5-free. Secondly, we show that every 3-γ _t -critical graph G of odd order is factor-critical if it is K _1,5-free. Finally, we show that G has a perfect matching if G is a K _1,4-free 4-γ _t (G)-critical graph of even order and G is factor-critical if G is a K _1,4-free 4-γ _t (G)-critical graph of odd order.     

Minimal 2-matching-covered graphs

A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle. A graph G is said to be 2-matching-covered if every edge of G lies in some perfect 2-matching of G. A 2-matching-covered graph is equivalent to a “regularizable” graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if G−e is not 2-matching-covered for all edges e of G. We use Berge’s theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than K₂ and K₄ is 2 and to prove that a minimal 2-matching-covered graph other than K₄ cannot contain a complete subgraph with at least 4 vertices.     

Regular factors in K1,n free graphs

A graph is said to be K_1,n-free, if it contains no K_1,n as an induced subgraph. We prove that for n ? 3 and r ? n ?1, if G is a K_1,n-free graph with minimum degree at least (n²/4(n ?1))r + (3n ?6)/2 + (n ?1)/4r, then G has an r-factor (in the case where r is even, the condition r ? n ?1 can be dropped).     

A note on balanced bipartitions

A balanced bipartition of a graph G is a bipartition V₁ and V₂ of V(G) such that −1≤|V₁|−|V₂|≤1. Bollobás and Scott conjectured that if G is a graph with m edges and minimum degree at least 2 then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤m/3, where e(V_i) denotes the number of edges of G with both ends in V_i. In this note, we prove this conjecture for graphs with average degree at least 6 or with minimum degree at least 5. Moreover, we show that if G is a graph with m edges and n vertices, and if the maximum degree Δ(G)=o(n) or the minimum degree δ(G)→∞, then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤(1+o(1))m/4, answering a question of Bollobás and Scott in the affirmative. We also provide a sharp lower bound on max{e(V₁,V₂):V₁,V₂ is a balanced bipartition of G}, in terms of size of a maximum matching, where e(V₁,V₂) denotes the number of edges between V₁ and V₂.     

Contractible edges in some k-connected graphs

An edge e of a k-connected graph G is said to be k-contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k-connected. In 2002, Kawarabayashi proved that for any odd integer k ? 5, if G is a k-connected graph and G contains no subgraph D = K ₁ + (K ₂ ∪ K _1,2), then G has a k-contractible edge. In this paper, by generalizing this result, we prove that for any integer t ? 3 and any odd integer k ? 2t + 1, if a k-connected graph G contains neither K ₁ + (K ₂ ∪ K _1,t ), nor K ₁ + (2K ₂ ∪ K _1,2), then G has a k-contractible edge.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

K3,3-free intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper we classify all finite groups whose intersection graphs are K_3,3-free.     

4-factors in 2-connected star-free graphs

Let t≥3 be an integer. We show that if G is a 2-connected K_1,t-free graph with minimum degree at least (3t+1)/2, then G has a 4-factor.     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

Long Cycles Generate the Cycle Space of a Graph

Let G be a 2-connected graph in which the degree of every vertex is at least d. We prove that the cycles of length at least d + 1 generate the cycle space of G, unless G ≌ K_d+1 and d is odd. As a corollary, we deduce that the cycles of length at least d + 1 generate the subspace of even cycles in G. We also establish the existence of odd cycles of length at least d + 1 in the case when G is not bipartite.A second result states: if G is 2-connected with chromatic number at least k, then the cycles of length at least k generate the cycle space of G, unless G ≌ K_k and k is even. Similar corollaries follow, among them a stronger version of a theorem of Erdös and Hajnal.     

Packing Triangles in K 4-Free Graphs

Paul Erd?s conjectured that every K ₄-free graph of order n and size ${k + \lfloor n^2/4\rfloor}$ contains at least k edge disjoint triangles. In this note, we prove that such a graph contains at least 32k/35 + o(n ²) edge disjoint triangles and prove his conjecture for k ≥  0.077n ².     

On a property of minimal triangulations

A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal (chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and only if H is edgeless, H is connected and is an induced subgraph of P₅, or H has two connected components and is an induced subgraph of 2P₃.This completes the results of Parra and Scheffler, who have shown that MT holds for H=P_k, the path on k vertices, if and only if k?5 [A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics 79 (1997) 171-188], and of Meister, who proved that MT holds for ?P₂, ? copies of a P₂, if and only if ??2 [D. Meister, A complete characterisation of minimal triangulations of 2K₂-free graphs, Discrete Mathematics 306 (2006) 3327-3333].     

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn^{1-(v_H-2)/(e_H-1)}(logn)^1/(e_H-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K _r,r with r≥5. When H is a complete graph K _s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn^2/(s+1)(logn)^1-1/(e_H-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.     

Degree-Light-Free Graphs and Hamiltonian Cycles

 Let G and H be graphs. G is said to be degree-light H-free if G is either H-free or, for every induced subgraph K of G with K≅H, and every {u,v}⊆K, d i s t _K (u,v)=2 implies max {d(u),d(v)}≥|V(G)|/2. In this paper, we will show that every 2-connected graph with either degree-light {K _1,3, P ₆}-free or degree-light {K _1,3, Z}-free is hamiltonian (with three exceptional graphs), where P ₆ is a path of order 6 and Z is obtained from P ₆ by adding an edge between the first and the third vertex of P ₆ (see Figure 1). Received: December 9, 1998?Final version received: July 21, 1999     

Almost claw-free graphs

We say that G is almost claw-free if the vertices that are centers of induced claws (K_1,3) in G are independent and their neighborhoods are 2-dominated. Clearly, every claw-free graph is almost claw-free. It is shown that (i) every even connected almost claw-free graph has a perfect matching and (ii) every nontrivial locally connected K_1,4-free almost claw-free graph is fully cycle extendable.     

Every 3-connected {K 1,3,N 3,3,3}-free graph is Hamiltonian

For non-negative integers i, j and k, let N _i,j,k be the graph obtained by identifying end vertices of three disjoint paths of lengths i, j and k to the vertices of a triangle. In this paper, we prove that every 3-connected {K _1,3,N _3,3,3}-free graph is Hamiltonian. This result is sharp in the sense that for any integer i > 3, there exist infinitely many 3-connected {K _1,3,N _i,3,3}-free non-Hamiltonian graphs.     

Packing and Covering Triangles in K 4-free Planar Graphs

We show that every K ₄-free planar graph with at most ν edge-disjoint triangles contains a set of at most ${\frac32\nu}$ edges whose removal makes the graph triangle-free. Moreover, equality is attained only when G is the edge-disjoint union of 5-wheels plus possibly some edges that are not in triangles. We also show that the same statement is true if instead of planar graphs we consider the class of graphs in which each edge belongs to at most two triangles. In contrast, it is known that for any c?<?2 there are K ₄-free graphs with at most ν edge-disjoint triangles that need more than cν edges to cover all triangles.