On stable cutsets in claw-free graphs and planar graphs

A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let $K_4$ and $K_{1,3}$ (claw) denote the complete (bipartite) graph on 4 and $1+3$ vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a $K_4$-free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, $K_4$)-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs.Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for $K_4$-free planar graphs with maximum degree five.     

Gear composition and the stable set polytope

We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of when G is claw-free.     

On cycle lengths in claw-free graphs with complete closure

We show a construction that gives an infinite family of claw-free graphs of connectivity κ=2,3,4,5 with complete closure and without a cycle of a given fixed length. This construction disproves a conjecture by the first author, A. Saito and R.H. Schelp.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

On 3-stable number conditions in n-connected claw-free graphs

For a subgraph $X$ of $G$, let ${\alpha }_G^3\left(X\right)$ be the maximum number of vertices of $X$ that are pairwise distance at least three in $G$. In this paper, we prove three theorems. Let $n$ be a positive integer, and let $H$ be a subgraph of an $n$-connected claw-free graph $G$. We prove that if $n\ge 2$, then either $H$ can be covered by a cycle in $G$, or there exists a cycle $C$ in $G$ such that ${\alpha }_G^3(H?V\left(C\right))\le {\alpha }_G^3\left(H\right)?n$. This result generalizes the result of Broersma and Lu that $G$ has a cycle covering all the vertices of $H$ if ${\alpha }_G^3\left(H\right)\le n$. We also prove that if $n\ge 1$, then either $H$ can be covered by a path in $G$, or there exists a path $P$ in $G$ such that ${\alpha }_G^3(H?V\left(P\right))\le {\alpha }_G^3\left(H\right)?n?1$. By using the second result, we prove the third result. For a tree $T$, a vertex of $T$ with degree one is called a leaf of $T$. For an integer $k\ge 2$, a tree which has at most $k$ leaves is called a $k$-ended tree. We prove that if ${\alpha }_G^3\left(H\right)\le n+k?1$, then $G$ has a $k$-ended tree covering all the vertices of $H$. This result gives a positive answer to the conjecture proposed by Kano et al. (2012).     

The asymptotic number of claw-free cubic graphs

Let H_n be the number of claw-free cubic graphs on 2n labeled nodes. In an earlier paper we characterized claw-free cubic graphs and derived a recurrence relation for H_n. Here we determine the asymptotic behavior of this sequence:

     

Circumferences and minimum degrees in 3-connected claw-free graphs

In this paper, we prove that every 3-connected claw-free graph G on n vertices contains a cycle of length at least min{n,6δ−15}, thereby generalizing several known results.     

Extremal problems on the Hamiltonicity of claw-free graphs

In 1962, Erd?s proved that if a graph $G$ with $n$ vertices satisfies

$e\left(G\right)>max\left\{\left(\genfrac{}{}{0ex}{}{n?k}{2}\right)+k^2,\left(\genfrac{}{}{0ex}{}{?(n+1)∕2?}{2}\right)+{?\frac{n?1}{2}?}^2\right\},$

where the minimum degree $\delta \left(G\right)\ge k$ and $1\le k\le (n?1)∕2$, then it is Hamiltonian. For $n\ge 2k+1$, let $E_n^k=K_k\vee (k{K}_1+K_{n?2k})$, where “$\vee$” is the “join” operation. One can observe $e\left(E_n^k\right)=\left(\genfrac{}{}{0ex}{}{n?k}{2}\right)+k^2$ and $E_n^k$ is not Hamiltonian. As $E_n^k$ contains induced claws for $k\ge 2$, a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of Erd?s’ theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include Ryjá?ek’s claw-free closure theory and Brousek’s characterization of minimal 2-connected claw-free non-Hamiltonian graphs.     

On hyperbolic Coxeter polytopes with mutually intersecting facets

We prove that, apart from some well-known low-dimensional examples, any compact hyperbolic Coxeter polytope has a pair of disjoint facets. This is one of very few known general results concerning combinatorics of compact hyperbolic Coxeter polytopes. We also obtain a similar result for simple non-compact polytopes.     

Connected even factors in claw-free graphs

A connected even [2,2s]-factor of a graph G is a connected factor with all vertices of degree i (i=2,4,…,2s), where s?1 is an integer. In this paper, we show that every supereulerian K_1,s-free graph (s?2) contains a connected even [2,2s-2]-factor, hereby generalizing the result that every 4-connected claw-free graph has a connected [2,4]-factor by Broersma, Kriesell and Ryjacek.     

On the number of components in 2-factors of claw-free graphs

In this paper, we prove that if a claw-free graph G with minimum degree δ?4 has no maximal clique of two vertices, then G has a 2-factor with at most (|G|-1)/4 components. This upper bound is best possible. Additionally, we give a family of claw-free graphs with minimum degree δ?4 in which every 2-factor contains more than n/δ components.     

Circumferences of regular claw-free graphs

A known result obtained independently by Fan and Jung is that every 3-connected k-regular graph on n vertices contains a cycle of length at least min{3k,n}. This raises the question of how much can be said about the circumferences of 3-connected k-regular claw-free graphs. In this paper, we show that every 3-connected k-regular claw-free graph on n vertices contains a cycle of length at least min{6k-17,n}.