3.1. Powers of Graphs

The kth power  of a connected graph G, where , is that graph with  for which .

  • is a square of G.
  • is a cube of G.

What can we say about the hamiltonicity of a power-graph?

Theorem 3.1.  is hamiltonian if G is hamiltonian.

Proof.

Since  contains G as a subgraph, the statement follows immediately.

On the other side, for any connected graph G - independently whether it is hamiltonian or not - of order at least 3 and for a sufficient large k, the graph  is hamiltonian since  is complete if G has diameter d.

What is the minimum k for which  is hamiltonian?

The next Figure shows an example where  is not hamiltonian, but  is hamiltonian.

Theorem 3.2. (Karaganis, 1968 Sekanina 1960): If G is a connected graph, then  is hamiltonian-connected.

Proof.

If H is a spanning tree of G and  is hamiltonian-connected, then  is hamiltonian-connected.

It is sufficient to prove that the cube of every tree is hamiltonian-connected.

We will show it by induction on n, the order of the tree.

  • For small values of n the result is obvious.
  • Assume for all trees H of order less than n that is hamiltonian-connected, and let T be a tree of order n, and let u and v be any two vertices of T.

Case 1: Suppose that u and v are adjacent in T.

Let e = uv, and consider the forest T-e. This forest has two compon-ents and containing u and v, respectively.

By the induction hypothesis and are hamiltonian-connected.

Let  be any vertex of  adjacent to u, and let  be any vertex of  adjacent to v. (If  or  is trivial, then we define  or , respectively.)

Since  so it is true that  and  are adjacent in .

Let  be a hamiltonian  path of and let  be a hamiltonian  path of.

The path formed by beginning with  followed by the edge  and then the path  is a hamiltonian  path of .

Case 2: Suppose that u and v are not adjacent in T.

Since T is a tree, there is a unique path between every two of its vertices. Let P be the unique  path of T, and let  be the edge which incident with u in P.

The graph  consists of two trees,  and  containing u and w, respectively.

By the induction hypothesis there exists a hamiltonian  path  in.

Let u1 be a vertex of  adjacent to u (or let  if  is trivial), and let  be a hamiltonian  path in.

Since , therefore the edge  is present in .

So, the path formed by starting with  followed by  and then  is a hamiltonian  path of .

Although it is not true that the squares of all connected graphs of order at least 3 are hamiltonian, it was conjectured by Nash-Williams and Plummer that for 2-connected graphs this is the case.

In 1974, Fleischner proved the conjecture to be correct.

Theorem 3.3. If G is 2-connected, then  is hamiltonian.

A graph G is k-(vertex)-connected  if

  • either
  • or it has at least vertices and no set of vertices separates G.

Theorem 3.4. If G is 2-connected, then  is hamiltonian-connected.

Proof.

Since G is 2-connected, it has order at least 3. Let u and v be any two vertices of G. Let  be distinct copies of G, and let  and  be the vertices in  corresponding u and v.

Let us form a new graph H by adding to  two new vertices  and  and ten new edges  and .

H is 2-connected since

  • neither nor is a cut-vertex of H,
  • each graphs is 2-connected and contains two vertices adjacent to vertices in ,
  • no vertex in is a cut-vertex of H.
  • Since H is 2-connected, then - by Theorem 5.23 - has a hamilton-ian cycle C. This cycle contains and .
  • At least one of the graphs contains no vertex adjacent to or on C. Let this graph be .

Since  and  are the only vertices which are adjacent on C to vertices not in , it follows that C has a  path containing all vertices of .

Thus has a hamiltonian  path, which implies that  contains a hamiltonian  path.

So,  is hamiltonian-connected.