Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components,...

We say that a spanning eulerian subgraph F ⊂ G is a flower in a graph G if there is a vertex u ∈ V(G) (called the center of F) such that all vertices of G except u are of the degree exactly 2 in F. A graph G has the flower property if every vertex of G is a center of a flower. Kaneko conjectured that G has the flower property if and only if G is hamiltonian. In the present paper we prove this conjecture in several special classes of graphs, among others in squares and in a certain...

If $G$ is a connected graph of order $n\ge 1$, then by a hamiltonian coloring of $G$ we mean a mapping $c$ of $V\left(G\right)$ into the set of all positive integers such that $|c\left(x\right)-c\left(y\right)|\ge n-1-D_G(x,y)$ (where $D_G(x,y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x,y\in V\left(G\right)$. Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $$min(max(c\left(z\right);z\in V\left(G\right)\left)\right),$$ where the minimum is taken over all hamiltonian colorings $c$ of $G$. The main result of this paper can be formulated as follows: Let $G$ be a connected graph of order $n\ge 3$. Assume that there exists a subgraph...

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.

For a nontrivial connected graph $G$ of order $n$ and a linear ordering $s{v}_1,v_2,...,v_n$ of vertices of $G$, define $d\left(s\right)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})$. The traceable number $t\left(G\right)$ of a graph $G$ is $t\left(G\right)=min\left\{d\right(s\left)\right\}$ and the upper traceable number $t^{+}\left(G\right)$ of $G$ is $t^{+}\left(G\right)=max\left\{d\left(s\right)\right\},$ where the minimum and maximum are taken over all linear orderings $s$ of vertices of $G$. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs $G$ for which $t^{+}\left(G\right)-t\left(G\right)=1$ are characterized and a formula for the upper...

A graph $G$ is called $\{H_1,H_2,\cdots ,H_k\}$-free if $G$ contains no induced subgraph isomorphic to any graph $H_i$, $1\le i\le k$. We define $${\sigma }_k=min\left\{\sum _{i=1}^{k}d\left(v_i\right):\{v_1,\cdots ,v_k\}\text{is}\text{an}\text{independent}\text{set}\text{of}\text{vertices}\text{in}G\right\}.$$ In this paper, we prove that (1) if $G$ is a connected $\{K_{1,4},K_{1,4}+e\}$-free graph of order $n$ and ${\sigma }_3\left(G\right)\ge n-1$, then $G$ is traceable, (2) if $G$ is a 2-connected $\{K_{1,4},K_{1,4}+e\}$-free graph of order $n$ and $|N\left(x_1\right)\cup N\left(x_2\right)|+|N\left(y_1\right)\cup N\left(y_2\right)|\ge n-1$ for any two distinct pairs of non-adjacent vertices $\{x_1,x_2\}$, $\{y_1,y_2\}$ of $G$, then $G$ is traceable, i.e., $G$ has a Hamilton path, where $K_{1,4}+e$ is a graph obtained by joining a pair of non-adjacent vertices in a $K_{1,4}$.

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