update :9/26/2010 12:29:00 PM    author :by MEHDI BEHZAD AND GARY CHARTRANDf    resource :(1) G. CHARTRAND, The existence of complete cycles in repeated linegraphs, Bull. Amer. Mat

Dr. Mehdi Behzad;An Iranian Mathematician

Mehdi Behzad is a mathematician of Iranian descent specializing in graph theory. He received his Ph.D. from Michigan State University in 1965.

TOTAL GRAPHS AND TRAVERSABILITY

"With every graph G (finite and undirected with no loops or multiple lines)

there is associated a graph L(G), called the line-graph of G, whose points
correspond in a one-to-one manner with the lines of G in such a way that two
points of L(G) are adjacent if and only if the corresponding lines of G are
adjacent. This concept was originated by Whitney (3). In a similar way one can
associate with G another graph which we call its total graph and denote by T(G).
This new graph has the property that a one-to-one correspondence can be
established between its points and the elements (the set of points and lines) of
G such that two points of T(G) are adjacent if and only if the corresponding
elements of G are adjacent (if both elements are points or both are lines) or
they are incident




'(if one element is a point and the other a line). In Fig. 1, a graph G and
its total graph T(G) are shown. In T(G) the " dark " points correspond to the
points of G while the " light " points correspond to the lines of G. The
linegraph L(G) is a subgraph of T(G) and consists of the " light" points and the
lines of T(G) joining two such points. These lines are drawn in Fig. 1 with
dashed lines. In this note we present characterisations of graphs having
Hamiltonian total graphs and of graphs whose total graphs are Eulerian. In
addition, we prove that for every non-trivial connected graph G, T(T(G)) is
Hamiltonian. A graph G is Hamiltonian if it has a Hamiltonian cycle, i.e. a
cycle containing .all points of G. (For a discussion of these graphs, the reader
is directed to t Work supported by the U.S. Air Force Office of Scientific
Research under grant AF-AFOSR-754-65.


Ore (2).) A necessary and sufficient condition for a graph whose total graph
is Hamiltonian is presented in our first theorem. Two elements a and b of G are
said to be neighbours if one of the following holds: (i) a and b are adjacent
points, (ii) a and b are adjacent lines, (iii) one of a and b is a point and the
other an incident line. A graph is trivial if it consists of a single point.
Theorem 1. The total graph T(G) of a non-trivial graph G is Hamiltonian if and
only if the set of all elements of G can be ordered in such a way that
consecutive elements are neighbours as are the first and last elements. Proof.
If the elements of G can be so appropriately ordered, then by taking the
corresponding points of T(G) in this same order, a Hamiltonian cycle is
produced. Conversely, if T(G) contains a Hamiltonian cycle then let at be that
element of G associated with the point Vr The ordering a0, au ..., «„_!, an = a0
has the desired properties. Theorem 2. A sufficient condition for T(G) to be
Hamiltonian is that G be Hamiltonian. Proof. Assume G has/? points and q lines,
and let C = (Vo, Vu ..., Vp = Fo) be a Hamiltonian cycle of G. We construct an
ordered sequence of the p+q elements of G such that consecutive elements are
neighbours and the last element is a neighbour of the first, as follows: Let Vo
be the first element of the sequence, and then select in any order all lines of
G incident to Vo which are not in C (if any), followed by the line V0Vy of C and
the point Vr. Next in the sequence, choose those lines (if any) which are
incident to V1 and not in C, followed by the line Vt V2 of C and the point V2-
This process is repeated, except that lines not in C are omitted in the ordering
if they have been previously included in the sequence. By this procedure, the
line FP_,FP of C is obtained as the final element of this sequence, and this
line is a neighbour of Vo. Thus by Theorem 1,. T(G) is Hamiltonian. By way of
notation, we let T2(G) denote T(T(G)) and, in general, T\G) = T(Tn-\G)) for n ^
2, where T^G) = T(G). Using induction and the result of Theorem 2,. we obtain an
immediate corollary. Corollary 2a. If G is Hamiltonian, then Tn(G) is
Hamiltonian for all n ^ 1.. In a Hamiltonian graph all its points can be
traversed with a single cycle. If a connected graph has the property that each
of its lines can be traversed exactly once with a single closed path in which
points may be encountered more than once, then the graph is called Eulerian. It
is well known that a graph is Eulerian if and only if it is connected and every
point has even degree, i.e. the number of incident lines with each point is
even. TOTAL GRAPHS AND TRAVERSABILITY U9 The following observation will prove
useful in our next theorem. Remark. If V is a point of G and V1 is the
corresponding point of T(G), then the degree of V1, denoted by deg V1, equals 2
deg V, while if X = VlV1 is a line of G and X1 is the corresponding point of
T(G), then deg A-1 = degK1+degF2. Theorem 3. Let G be a connected graph. Then
T(G) is Eulerian if and only if all points of G are of the same parity. Proof.
By the parity of point we mean the parity of its degree. Let T(G) be an Eulerian
graph, and assume, to the contrary, that G has a point Vx with odd degree and a
point V2 with even degree. Since G is connected, Vx and V2 are joined by a path
on which exist two adjacent points V3 and VA of opposite parity. Thus, by the
preceding remark, the point in T(G) which corresponds to the line F3F4 has odd
degree, which contradicts the fact that T(G) is Eulerian. The converse is a
direct consequence of the remark. Corollary 3a. If G is Eulerian, then T(G) is
Eulerian. Even if all points of a connected graph are not of the same parity,
then T(G) contains an Eulerian subgraph of a special type. A subgraph H of a
graph G is a spanning subgraph if it contains all the points of G. Theorem 4.
The total graph T(G) of every connected graph G contains a spanning Eulerian
subgraph. Proof. The result is obvious if G consists of a single point.
Otherwise, the connected spanning subgraph H of T(G) obtained by deleting all
lines of the line-graph L(G) is Eulerian since all its points have even degree.
Theorem 5. If a non-trivial graph G contains a spanning Eulerian subgraph, then
T(G) is Hamiltonian. Proof. Let S be a spanning Eulerian subgraph of G. The
lines of S can be arranged in a cyclic fashion C = {Xo, Xu ..., Xr-X, Xr = Xo);
we let Vt be that point incident with the lines Xt and Xt + 1, i = 0, 1, ..., r—
1. Of course, some of the points Vx may be identical. We construct an ordered
sequence of elements of G such that consecutive elements are neighbours and the
last element is a neighbour of the first as follows: Let Xo be the first term of
the sequence, Vo the second, and then follow these by all lines of G incident to
VQ. which are not in C (if any). These elements are followed by Xu Vu and all
those lines of G which are incident to Vx and not in C (if any). This procedure
is continued except that lines and points are omitted from the sequence if they
have been previously included in the sequence. Finally, the line Xr_t of C will
be in the sequence followed by the point Kr_ t if it has not been previously
taken. But in any case Xo is a neighbour of both Vr^l and Xr.x. By Theorem 1,
T(G) is Hamiltonian. Corollary 5a. If G is Eulerian, then T{G) is Eulerian and
Hamiltonian. 120 M. BEHZAD AND G. CHARTRAND It follows by Theorem 4 that if G is
a non-trivial connected graph, then T(G) has a spanning Eulerian subgraph,
which, according to Theorem 5, implies that T(T(G)) is Hamiltonian. This result
is stated below. Theorem 6. If G is a non-trivial connected graph, then T2(G) is
Hamiltonian. Corollary 6a. If G is a non-trivial connected graph, then T"(G) is
Hamiltonian Jor all n^2. This corollary serves as an analogue to the theorem in
(1) which states that if G is a connected non-trivial graph, with p points which
is not a simple path, then the iterated line-graph L"(G) is Hamiltonian for all
n^p — 3. The •conclusion of Corollary 6a cannot, in general, be improved since,
for example, the graph G of Fig. 1 is non-trivial and connected but T(G) is not
Hamiltonian.