Hamiltonian circuits in N2-locally connected K1,3-free graphs

There are many results concerned with the hamiltonicity of K_1,3-free graphs. In the paper we show that one of the sufficient conditions for the K_1,3-free graph to be Hamiltonian can be improved using the concept of second-type vertex neighborhood. The paper is concluded with a conjecture.     

Regular factors in K1,3-free graphs

We show that every connected K_1,3-free graph with minimum degree at least 2k contains a k-factor and construct connected K_1,3-free graphs with minimum degree k + 0(√k) that have no k-factor.     

Forbidden subgraphs and hamiitonian properties in the square of a connected graph

Various Harniltonian-like properties are investigated in the squares of connected graphs free of some set of forbidden subgraphs. The star K_1,4 the subdivision graph of K_1,3, and the subdivision graph of K_1,3 minus an endvertex play central roles. In particular, we show that connected graphs free of the subdivision graph of K_1,3 minus an endvertex have vertex pancyclic squares.     

On connected factors inK 1,3-free graphs

A graph is said to beK _1,3-free if it contains noK _1,3 as an induced subgraph. It is shown in this paper that every 2-connectedK _1,3-free graph contains a connected [2,3]-factor. We also obtain that every connectedK _1,3-free graph has a spanning tree with maximum degree at most 3. This research is partially supported by the National Natural Sciences Foundation of China and by the Natural Sciences Foundation of Shandong Province of China.     

Longest paths and cycles in K1,3-free graphs

In this article we show that the standard results concerning longest paths and cycles in graphs can be improved for K_1,3-free graphs. We obtain as a consequence of these results conditions for the existence of a hamiltonian path and cycle in K_1,3-free graphs.     

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.     

A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity

Sumner [7] proved that every connected K _1,3-free graph of even order has a perfect matching. He also considered graphs of higher connectivity and proved that if m ≥ 2, every m-connected K _1,m+1-free graph of even order has a perfect matching. In [6], two of the present authors obtained a converse of sorts to Sumner’s result by asking what single graph one can forbid to force the existence of a perfect matching in an m-connected graph of even order and proved that a star is the only possibility. In [2], Fujita et al. extended this work by considering pairs of forbidden subgraphs which force the existence of a perfect matching in a connected graph of even order. But they did not settle the same problem for graphs of higher connectivity. In this paper, we give an answer to this problem. Together with the result in [2], a complete characterization of the pairs is given.     

On stable set polyhedra for K1,3-free graphs

We give several classes of facets for the convex hull of incidence vectors of stable sets in a K_1,3-free graph, including facets with (a, a + 1)-valued coefficients, where a = 1, 2, 3,…. These provide counterexamples to three recent conjectures concerning such facets. We also give a necessary and sufficient condition for a minimal imperfect graph to be an odd hole or an odd antihole and indicate that minimal imperfect K_1,3-free graphs satisfy the condition.     

A generalization of Dirac’s theorem for K(1,3)-free graphs

It is known that if a 2-connected graphG of sufficiently large ordern satisfies the property that the union of the neighborhoods of each pair of vertices has cardinality at leastn/2, thenG is hamiltonian. In this paper, we obtain a similar generalization of Dirac’s Theorem forK(1,3)-free graphs. In particular, we show that ifG is a 2-connectedK(1,3)-free graph of ordern with the cardinality of the union of the neighborhoods of each pair of vertices at least (n+1)/3, thenG is hamiltonian. We also investigate several other related properties inK(1,3)-free graphs such as traceability, hamiltonian-connectedness, and pancyclicity. Partially Supported by O. N. R. Contract Number N00014-88-K-0070. Partially Supported by O. N. R. Contract Number N00014-85-K-0694.     

The binding number of a graph and its cliques

We consider the binding numbers of K_r-free graphs, and improve the upper bounds on the binding number which force a graph to contain a clique of order r. For the case r=4, we provide a construction for K₄-free graphs which have a larger binding number than the previously known constructions. This leads to a counterexample to a conjecture by Caro regarding the neighborhoods of independent sets.     

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     

The square of a connected S(K1,3)-free graph is vertex pancyclic

We prove the conjecture of Gould and Jacobson that a connected S(K_1,3)-free graph has a vertex pancyclic square. Since S(K_1,3)² is not vertex pan-cyclic, this result is best possible.     

Every connected,locally connected nontrivial graph with no induced claw is hamiltonian

A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on p ≥ 3 vertices and having no induced K_1,3 is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtained as corollaries.     

Perfect Matchings in Total Domination Critical Graphs

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination number. A 3 _t EC graph is a total domination edge-critical graph with total domination number 3 and a 3 _t VC graph is a total domination vertex-critical graph with total domination number 3. A graph G is factor-critical if G − v has a perfect matching for every vertex v in G. In this paper, we show that every 3 _t EC graph of even order has a perfect matching, while every 3 _t EC graph of odd order with no cut-vertex is factor-critical. We also show that every 3 _t VC graph of even order that is K _1,7-free has a perfect matching, while every 3 _t VC graph of odd order that is K _1,6-free is factor-critical. We show that these results are tight in the sense that there exist 3 _t VC graphs of even order with no perfect matching that are K _1,8-free and 3 _t VC graphs of odd order that are K _1,7-free but not factor-critical.     

Hamiltonicity for K1, r-free graphs

In this paper, we investigate the Hamiltonicity of K_1,r-free graphs with some degree conditions. In particular, let G be a k-connected grph of order n≧3 which is K_1,4-free. If for every independent set {v₀, v₁, …, v_k} then G is hamiltonian. We use an upper bound for the independence number of K_1,r-free graphs to extent the above result to K_1,r-free graphs. Hamiltonian connected and, more generally, q-edge hamiltonian properties are studied here as well. © 1995 John Wiley & Sons, Inc.     

Minimal claw-free graphs

A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K _1,3 (claw) as an induced subgraph and if, for each edge e of G, G ™ e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs. Support by the South African National Research Foundation is gratefully acknowledged.     

Small graphs with chromatic number 5: A computer search

In this article we give examples of a triangle-free graph on 22 vertices with chromatic number 5 and a K₄-free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5-critical graphs on 9 vertices are exhibited. © 1995 John Wiley & Sons, Inc.     

Forbidden induced subgraphs for star-free graphs

Let H be a family of connected graphs. A graph G is said to be H-free if G is H-free for every graph H in H. In Aldred et al. (2010) [1], it was pointed that there is a family of connected graphs H not containing any induced subgraph of the claw having the property that the set of H-free connected graphs containing a claw is finite, provided also that those graphs have minimum degree at least 2 and maximum degree at least 3. In the same work, it was also asked whether there are other families with the same property. In this paper, we answer this question by solving a wider problem. We consider not only claw-free graphs but the more general class of star-free graphs. Concretely, given t≥3, we characterize all the graph families H such that every large enough H-free connected graph is K_1,t-free. Additionally, for the case t=3, we show the families that one gets when adding the condition ∣H∣≤k for each positive integer k.     

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.     

A necessary and sufficient condition for connected,locally k-connected k1,3-free graphs to be k-hamiltonian

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K_1,3-free graph is k-hamiltonian if and only if it is (k + 2)-connected (K ? 1).