Advanced Search

The Ryjáček closure is a powerful tool in the study of Hamiltonian properties of claw-free graphs. Because of its usefulness, we may hope to use it in the classes of graphs defined by another forbidden subgraph. In this note, we give a negative answer to this hope, and show that the claw is the only forbidden subgraph that produces non-trivial results on Hamiltonicity by the use of the Ryjáček closure.

In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.

An edge of $G$ is singular if it does not lie on any triangle of $G$; otherwise, it is non-singular. A vertex $u$ of a graph $G$ is called locally connected if the induced subgraph $G\left[N\right(u\left)\right]$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph $G$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex $v$ of degree at least $3$ in $G,$ there is a nonnegative integer $s$ such that $v$ lies...

The line graph of a graph $G$, denoted by $L\left(G\right)$, has $E\left(G\right)$ as its vertex set, where two vertices in $L\left(G\right)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$, define ${\overline{\sigma }}_2\left(H\right)=min\{d\left(u\right)+d\left(v\right):uv\in E\left(H\right)\}$. Let $H$ be a 2-connected claw-free simple graph of order $n$ with $\delta \left(H\right)\ge 3$. We show that, if ${\overline{\sigma }}_2\left(H\right)\ge \frac{1}{7}(2n-5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček’s closure $\mathrm{cl}\left(H\right)=L\left(G\right)$, where $G$ is an essentially $2$-edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10 which have...

Let $G=\left(V\right(G),E(G\left)\right)$ be a graph. Gould and Hynds (1999) showed a well-known characterization of $G$ by its line graph $L\left(G\right)$ that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph $G$ to have a 2-factor in its line graph $L\left(G\right).$ A graph $G$ is called $N^2$-locally connected if for every vertex $x\in V\left(G\right),$ $G\left[\{y\in V\left(G\right)1\le {\mathrm{dist}}_G(x,y)\le 2\}\right]$ is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which every vertex...