"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.