We prove that for every number $n\ge 1$, the $n$-iterated $P_3$-path graph of $G$ is isomorphic to $G$ if and only if $G$ is a collection of cycles, each of length at least 4. Hence, $G$ is isomorphic to $P_3\left(G\right)$ if and only if $G$ is a collection of cycles, each of length at least 4. Moreover, for $k\ge 4$ we reduce the problem of characterizing graphs $G$ such that $P_k\left(G\right)\cong G$ to graphs without cycles of length exceeding $k$.

For any $n\ge 1$ and any $k\ge 1$, a graph $S(n,k)$ is introduced. Vertices of $S(n,k)$ are $n$-tuples over $\{1,2,...,k\}$ and two $n$-tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs $S(n,3)$ are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of $S(n,k)$. Together with a formula for the distance, this result is used to compute the distance between two vertices in...

Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H). Adopting the terminology introduced by Broersma et al. and Čada, a graph G is called 1-heavy if at least one of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has degree at least n/2, and is called claw-heavy if each claw of G has a pair of end vertices with degree sum at least...

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

The family of 5-valent polyhedral graphs whose faces are all triangles or 3s-gons, s ≥ 9, is shown to contain non-hamiltonian graphs and to have a shortness exponent smaller than one.

Following a problem posed by Lovász in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a $(2,s,3)$-presentation, that is, for groups $G=\langle a,b\mid a^2=1,b^s=1,{\left(ab\right)}^3=1,\cdots \rangle$ generated by an involution $a$ and an element $b$ of order $s\ge 3$ such that their product $ab$ has order $3$. More precisely, it is shown that the Cayley graph $X=Cay(G,\{a,b,b^{-1}\})$ has a Hamilton cycle when $\left|G\right|$ (and thus $s$) is congruent to 2 modulo 4, and has a long cycle missing...

Let G be a graph on n vertices. A vertex of G with degree at least n/2 is called a heavy vertex, and a cycle of G which contains all the heavy vertices of G is called a heavy cycle. In this note, we characterize graphs which contain no heavy cycles. For a given graph H, we say that G is H-heavy if every induced subgraph of G isomorphic to H contains two nonadjacent vertices with degree sum at least n. We find all the connected graphs S such that a 2-connected graph G being S-heavy implies any longest...