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.     

Forbidden subgraphs that imply 2-factors

The connected forbidden subgraphs and pairs of connected forbidden subgraphs that imply a 2-connected graph is hamiltonian have been characterized by Bedrossian [Forbidden subgraph and minimum degree conditions for hamiltonicity, Ph.D. Thesis, Memphis State University, 1991], and extensions of these excluding graphs for general graphs of order at least 10 were proved by Faudree and Gould [Characterizing forbidden pairs for Hamiltonian properties, Discrete Math. 173 (1997) 45-60]. In this paper a complete characterization of connected forbidden subgraphs and pairs of connected forbidden subgraphs that imply a 2-connected graph of order at least 10 has a 2-factor will be proved. In particular it will be shown that the characterization for 2-factors is very similar to that for hamiltonian cycles, except there are seven additional pairs. In the case of graphs of all possible orders, there are four additional forbidden pairs not in the hamiltonian characterization, but a claw is part of each pair.     

Cycles with a chord in dense graphs

A cycle of order $k$ is called a $k$-cycle. A non-induced cycle is called a chorded cycle. Let $n$ be an integer with $n\ge 4$. Then a graph $G$ of order $n$ is chorded pancyclic if $G$ contains a chorded $k$-cycle for every integer $k$ with $4\le k\le n$. Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order $n$ satisfying ${deg}_{G}u+{deg}_{G}v\ge n$ for every pair of nonadjacent vertices $u$,  $v$ in $G$ is chorded pancyclic unless $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, the Cartesian product of $K_3$ and $K_2$. They also conjectured that if $G$ is Hamiltonian, we can replace the degree sum condition with the weaker density condition $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph $G$ of order $n$ with $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ contains a $k$-cycle, then $G$ contains a chorded $k$-cycle, unless $k=4$ and $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, Then observing that $K_{\frac{n}{2},\frac{n}{2}}$ and $K_3\square K_2$ are exceptions only for $k=4$, we further relax the density condition for sufficiently large $k$.     

Forbidden subgraphs that imply hamiltonian‐connectedness*

It is proven that if G is a 3‐connected claw‐free graph which is also H₁‐free (where H₁ consists of two disjoint triangles connected by an edge), then G is hamiltonian‐connected. Also, examples will be described that determine a finite family of graphs such that if a 3‐connected graph being claw‐free and L‐free implies G is hamiltonian‐connected, then L . © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 104–119, 2002     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

On the number of independent chorded cycles in a graph

Hajnal and Corrádi proved that any simple graph on at least 3k vertices with minimal degree at least 2k contains k independent cycles. We prove the analogous result for chorded cycles. Let G be a simple graph with |V(G)|4k and minimal degree δ(G)3k. Then G contains k independent chorded cycles. This result is sharp.     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3. At the workshop C&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z₁ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.     

Forbidden Induced Subgraphs for Toughness

Let be a family of connected graphs. A graph G is said to be ‐free if G is H‐free for every graph H in . We study the relation between forbidden subgraphs in a connected graph G and the resulting toughness of G. In particular, we consider the problem of characterizing the graph families such that every large enough connected ‐free graph is t‐tough. In this article, we solve this problem for every real positive number t. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 191–202, 2013     

On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs

Let H be a set of graphs. A graph is called H-free if it does not contain a copy of a member of H as an induced subgraph. If H is a graph then G is called H-free if it is {H}-free. Plummer, Stiebitz, and Toft proved that, for every -free graph H on at most four vertices, every -free graph G has a collection of ⌈|V(G)|/2⌉ many pairwise adjacent vertices and edges (where a vertexvand an edgeeare adjacent if v is disjoint from the set V(e) of endvertices of e and adjacent to some vertex of V(e), and two edgeseandfare adjacent if V(e) and V(f) are disjoint and some vertex of V(e) is adjacent to some vertex of V(f)). Here we generalize this statement to -free graphs H on at most five vertices.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.