Degree and neighborhood conditions for hamiltonicity of claw-free graphs

For a graph $H$, let ${\sigma }_t\left(H\right)=min\left\{{\Sigma }_{i=1}^t{d}_H\left(v_i\right)\right|\{v_1,v_2,\dots ,v_t\}\text{is an independent set in }H\}$ and let $U_t\left(H\right)=min\left\{\right|{?}_{i=1}^t{N}_H\left(v_i\right)\left|\right|\{v_1,v_2,?,v_t\}\text{is an independent set in }H\}$. We show that for a given number $?$ and given integers $p\ge t>0$, $k\in \{2,3\}$ and $N=N(p,?)$, if $H$ is a $k$-connected claw-free graph of order $n>N$ with $\delta \left(H\right)\ge 3$ and its Ryjác?ek’s closure $cl\left(H\right)=L\left(G\right)$, and if $d_t\left(H\right)\ge t(n+?)∕p$ where $d_t\left(H\right)\in \{{\sigma }_t\left(H\right),U_t\left(H\right)\}$, then either $H$ is Hamiltonian or $G$, the preimage of $L\left(G\right)$, can be contracted to a $k$-edge-connected $K_3$-free graph of order at most $max\{4p?5,2p+1\}$ and without spanning closed trails. As applications, we prove the following for such graphs $H$ of order $n$ with $n$ sufficiently large:(i) If $k=2$, $\delta \left(H\right)\ge 3$, and for a given $t$ ($1\le t\le 4$) $d_t\left(H\right)\ge \frac{tn}{4}$, then either $H$ is Hamiltonian or $cl\left(H\right)=L\left(G\right)$ where $G$ is a graph obtained from $K_{2,3}$ by replacing each of the degree 2 vertices by a $K_{1,s}$ ($s\ge 1$). When $t=4$ and $d_t\left(H\right)={\sigma }_4\left(H\right)$, this proves a conjecture in Frydrych (2001).(ii) If $k=3$, $\delta \left(H\right)\ge 24$, and for a given $t$ ($1\le t\le 10$) $d_t\left(H\right)>\frac{t(n+5)}{10}$, then $H$ is Hamiltonian. These bounds on $d_t\left(H\right)$ in (i) and (ii) are sharp. It unifies and improves several prior results on conditions involved ${\sigma }_t$ and $U_t$ for the hamiltonicity of claw-free graphs. Since the number of graphs of orders at most $max\{4p?5,2p+1\}$ are fixed for given $p$, improvements to (i) or (ii) by increasing the value of $p$ are possible with the help of a computer.     

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 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.     

NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF CLAW-FREE GRAPHS

Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)＞n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too.     

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}.     

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.     

The structure of even factors in claw-free graphs

Recently, Jackson and Yoshimoto proved that every bridgeless simple graph G with δ(G)≥3 has an even factor in which every component has order at least four, which strengthens a classical result of Petersen. In this paper, we give a strengthening of the above result and show that the above graphs have an even factor in which every component has order at least four that does not contain any given edge. We also extend the above result to the graphs with minimum degree at least three such that all bridges lie in a common path and to the bridgeless graphs that have at most two vertices of degree two respectively. Finally we use this extended result to show that every simple claw-free graph G of order n with δ(G)≥3 has an even factor with at most components. The upper bound is best possible.     

Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices

We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G)?5 has a Hamiltonian circuit if and only if the matrix A+I can be permuted on rows such that each column has at most (or exactly) k-1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A+I can be permuted on rows to have at most (or exactly) k-1 linear blocks per column.Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255-265]; Flammini et al. showed its NP-completeness for general k [Algorithmica 16 (1996) 549-568]; and Goldberg et al. proved the same for every fixed k?2 [J. Comput. Biol. 2 (1) (1995) 139-152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k?2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row.     

Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is Ω(n^0.694), and the circumference of a 3-connected claw-free graph is Ω(n^0.121). We generalize and improve the first result by showing that every 3-edge-connected graph with m edges has an Eulerian subgraph with Ω(m^0.753) edges. We use this result together with the Ryjá?ek closure operation to improve the lower bound on the circumference of a 3-connected claw-free graph to Ω(n^0.753). Our proofs imply polynomial time algorithms for finding large Eulerian subgraphs of 3-edge-connected graphs and long cycles in 3-connected claw-free graphs.     

Hamiltonicity and pancyclicity of cartesian products of graphs

The cartesian product of a graph G with K₂ is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g^′(H) and Δ(H)≤g^′(G) (we denote by g^′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian.     

无爪图上团横贯数的界

设 G=(V,E) 为简单图,图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交,即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目,记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.     

图的能量与哈密尔顿性

设G是一个无向简单图, A(G)为$G$的邻接矩阵. 用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件; 其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件. 这些结果改进了一些已知的结果.     

图的能量与哈密尔顿性

设G是一个无向简单图,A（G）为G的邻接矩阵．用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件：其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件．这些结果改进了一些已知的结果．     

Pancyclicity mod k of claw-free graphs and K1,4-free graphs

For any natural number k, a graph G is said to be pancyclic mod k if it contains a cycle of every length modulo k. In this paper, we show that every K_1,4-free graph G with minimum degree δ(G)k+3 is pancyclic mod k and every claw-free graph G with δ(G)k+1 is pancyclic mod k, which confirms Thomassen's conjecture (J. Graph Theory 7 (1983) 261–271) for claw-free graphs.     

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).