Geodesics and steps in a connected graph
We prove that for every number , the -iterated -path graph of is isomorphic to if and only if is a collection of cycles, each of length at least 4. Hence, is isomorphic to if and only if is a collection of cycles, each of length at least 4. Moreover, for we reduce the problem of characterizing graphs such that to graphs without cycles of length exceeding .
For any and any , a graph is introduced. Vertices of are -tuples over and two -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 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 . 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 of order we mean a mapping of into the set of all positive integers such that (where denotes the length of a longest path in ) for all distinct . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order with circumference .
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 -presentation, that is, for groups generated by an involution and an element of order such that their product has order . More precisely, it is shown that the Cayley graph has a Hamilton cycle when (and thus ) 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...