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

Ladislav Nebeský

Displaying similar documents to “The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs”

Hamiltonian colorings of graphs with long cycles

Ladislav Nebeský (2003)

Mathematica Bohemica

Similarity:

By a hamiltonian coloring of a connected graph $G$ of order $n \geq 1$ 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 G$ . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order $n \geq 5$ with circumference $n - 2$ .

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:

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

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

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

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

The $k$ -metric colorings of a graph

Futaba Fujie-Okamoto, Willem Renzema, Ping Zhang (2012)

Mathematica Bohemica

Similarity:

For a nontrivial connected graph $G$ of order $n$ , the detour distance $D (u, v)$ between two vertices $u$ and $v$ in $G$ is the length of a longest $u - v$ path in $G$ . Detour distance is a metric on the vertex set of $G$ . For each integer $k$ with $1 \leq k \leq n - 1$ , a coloring $c : V (G) \to ℕ$ is a $k$ -metric coloring of $G$ if $| c (u) - c (v) | + D (u, v) \geq k + 1$ for every two distinct vertices $u$ and $v$ of $G$ . The value $χ_{m}^{k} (c)$ of a $k$ -metric coloring $c$ is the maximum color assigned by $c$ to a vertex of $G$ and the $k$ -metric chromatic number $χ_{m}^{k} (G)$ of $G$ is the minimum value of a $k$ -metric coloring...