Hamiltonian colorings of graphs with long cycles

Ladislav Nebeský

The search session has expired. Please query the service again.

Displaying similar documents to “Hamiltonian colorings of graphs with long cycles”

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

Similarity:

If $G$ is a connected graph of order $n \geq 1$ , then by a hamiltonian coloring of $G$ we mean a mapping $c$ of $V (G)$ into the set of all positive integers such that $| c (x) - c (y) | \geq 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 (G)$ . Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $min (max (c (z); z \in V (G))),$ 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 \geq 3$ . Assume that there exists...

A note on a new condition implying pancyclism

Evelyne Flandrin, Hao Li, Antoni Marczyk, Mariusz Woźniak (2001)

Discussiones Mathematicae Graph Theory

Similarity:

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to $K_{n / 2, n / 2}$ .

Extension of several sufficient conditions for Hamiltonian graphs

Ahmed Ainouche (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph $(K_{r} \cup K ₛ \cup K ₜ) \lor K ₂$ , 1 ≤ r ≤ s ≤ t or the graph $((n + 1) / 2) K ₁ \lor K_{(n - 1) / 2}$ . It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity...

Factors and circuits in $K_{1, 3}$ -free graphs

Zdeněk Ryjáček (1989)

Banach Center Publications

Similarity:

Variations on a sufficient condition for Hamiltonian graphs

Ahmed Ainouche, Serge Lapiquonne (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition $N_{G} (x) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup x$ . In particular, this condition is satisfied if x does not center a claw (an induced $K_{1, 3}$ ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian...

Measures of traceability in graphs

Varaporn Saenpholphat, Futaba Okamoto, Ping Zhang (2006)

Mathematica Bohemica

Similarity:

For a connected graph $G$ of order $n \geq 3$ and an ordering $s v_{1}$ , $v_{2}, \dots, v_{n}$ of the vertices of $G$ , $d (s) = \sum_{i = 1}^{n - 1} d (v_{i}, v_{i + 1})$ , where $d (v_{i}, v_{i + 1})$ is the distance between $v_{i}$ and $v_{i + 1}$ . The traceable number $t (G)$ of $G$ is defined by $t (G) = min \}d (s)\{,$ where the minimum is taken over all sequences $s$ of the elements of $V (G)$ . It is shown that if $G$ is a nontrivial connected graph of order $n$ such that $l$ is the length of a longest path in $G$ and $p$ is the maximum size of a spanning linear forest in $G$ , then $2 n - 2 - p \leq t (G) \leq 2 n - 2 - l$ and both these bounds are sharp. We establish a formula for the traceable...

Extremal problems for forbidden pairs that imply hamiltonicity

Ralph Faudree, András Gyárfás (1999)

Discussiones Mathematicae Graph Theory

Similarity:

Let C denote the claw $K_{1, 3}$ , N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and $Z_{i}$ the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free...

Problems remaining NP-complete for sparse or dense graphs

Ingo Schiermeyer (1995)

Discussiones Mathematicae Graph Theory

Similarity:

For each fixed pair α,c > 0 let INDEPENDENT SET ( $m \leq c n^{α}$ ) and INDEPENDENT SET ( $m \geq (ⁿ ₂) - c n^{α}$ ) be the problem INDEPENDENT SET restricted to graphs on n vertices with $m \leq c n^{α}$ or $m \geq (ⁿ ₂) - c n^{α}$ edges, respectively. Analogously, HAMILTONIAN CIRCUIT ( $m \leq n + c n^{α}$ ) and HAMILTONIAN PATH ( $m \leq n + c n^{α}$ ) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with $m \leq n + c n^{α}$ edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH...