Hamiltonicity of the Double Vertex Graph and the Complete Double Vertex Graph of some Join Graphs

Abstract: Let

G

be a simple graph of order

n

. The double vertex graph

F_{2} (G)

of

G

is the graph whose vertices are the

2

-subsets of

V (G)

, where two vertices are adjacent in

F_{2} (G)

if their symmetric difference is a pair of adjacent vertices in

G

. A generalization of this graph is the complete double vertex graph

M_{2} (G)

of

G

, defined as the graph whose vertices are the

2

-multisubsets of

V (G)

, and two of such vertices are adjacent in

M_{2} (G)

if their symmetric difference (as multisets) is a pair of adjacent vertices in

G

. In this paper we exhibit an infinite family of graphs (containing Hamiltonian and non-Hamiltonian graphs) for which

F_{2} (G)

and

M_{2} (G)

are Hamiltonian. This family of graphs is the set of join graphs

G = G_{1} + G_{2}

, where

G_{1}

and

G_{2}

are of order

m g e q 1

and

n g e q 2

, respectively, and

G_{2}

has a Hamiltonian path. For this family of graphs, we show that if

m l e q 2 n

then

F_{2} (G)

is Hamiltonian, and if

m l e q 2 (n - 1)

then

M_{2} (G)

is Hamiltonian.

This page was built for publication: Hamiltonicity of the Double Vertex Graph and the Complete Double Vertex Graph of some Join Graphs