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.