CO?.IBINATOI~IAI, ASALYYIS  u                                  66-72

cyclcs; if there are no cycles or if all cycles have pseudo-
length 0, then the indes is taken to be 0. Typical results :
(1) If in the graph G each connected component has a cycle
whose pseudolength is not 0, then the set of all stable
equivalences on G forms a lattice. (2) If G and H are con-
nected graphs each of whose vertices is the endpoint of
mm di~eated edge, then the number of cennaeted nam-
ponents of the graph 0 x H is the greatest common divisor
of the indes of G and the index of H. The seconc; result
was obtained earlier for strongly connected oriented
graphs by &Andrew [Proc. Amer. Math. Sot. 14 (l!iO9),
600-606; JIR 27 #1932].   G. N. Raney (Storm, Conn.)

Hahn, Rudolf                            65
Graphen ohne unendliche Wege.
,11&h. Nachr. 31 (1966), 111-123.
The author characterizes the graphs having no infinite
paths. He finds that for a graph to be of this kind it must
be decomposable into finite graphs whose intersections
satisfy certain specified conditions. Moreover, these con-
ditions exhibit the finite graphs as the vertices of a tree,
and this tree must itself have no infinite path.
             W. T. Tutte (Waterloo, Ont.)

Harary, Frank; Nash-Williams, C. St. J. A.         66
On eulerian and hamiltonian graphs and Iine graphs.
Canad. Math. Bull. 8 (1965), 701-709.
The line graph L(G) is the incidence graph of the edges of
G. Additional graphs L,(G) (n B 2) are defined, and some
relationships between Eulerian and Hamiltonian proper-
ties of G, L(G), and the graphs L,,(G) are found. (The
reader may find it helpful to note that L,(G) = L(M,(G)),
where XI,(G) is the graph obtained from G by replacing
each edge of G by a path consisting of n edges; thus L,
is not the nth iterate of L.)

D. W. Walkup (Seattle, Wash.)

Have], Ivan                               67
Cn the completeness-number of a finite graph.  (Czech
and Russian summaries)

Casopis P&t. Mat. 90 (1965), 191-193.

The author calls two distinct edges of a graph G quasi-
neighbours if they both belong to some complete subgraph
of G. He defines a graph G' in which the vertices correspond
to the edges of G, and two vertices of G' are joined if and
only if the corresponding edges of G are not quasi-neigh-
bours. He shows that the minimum number of complete
subgraphs of G whose union is G is equal to the chromatic
number of G'.       W. T. Tutte (Waterloo, Ont.)

Hoffman, A. J.; McAndrew, M. H.
The polynomial of a directed graph.
Proc. Amer. Math. Sot. 16 (1965), 303-309.

68

Let G be a directed graph and A the adjacency matrix of
G. It is proved that there exists L polynomial P(x) such
that P(A) =J (when J is the matrix consisting entirely of
l's) if and only if G is strongly connected and strongly
regular. (G is strongly regular if for each vertex i the
number of edges with initial vertex i equals the number of
edges with terminal vertex i ; G is strongly connected if
for any vertices i, j (i#j), there is a directed path from i

to j.) The unique polynomial of least degree satisfying
I-`(A) = J (called the polynomial belonging to G) is charac-
terizcd in terms of the minimum polynomial of A.

Does the polynomial belonging to G determine G up to
isomorphism? This problem is studied for a particular
class of directed graphs. Let t be a positive integer and let
(Tt be the gmljh whose vertioes are all OF&FIX~ pairs (i, j)
of residues mod t and whose edges go from (i, j) to (i, j -t- 1)
and (i + 1,j) for all i, j. Let P,(x) be the polynomial
belonging to G,. The following theorem is proved : If t is a
prime or t = 4 and if H is a graph with ta vertices such that
Pi(x) belongs to II, then H zGc,.

J. K. GoZdhaber (College Park, Md.)

Troy, II. J.
On traversing graphs.

69

Amer. Math. Monthly 73 (1966), 497-499.

A covering of a graph G is a cyclic edge sequence S such
that consecutive edges in S are different and each edge in
G appears exactly twice in S, once in each direction. The
main result is that a graph in which all valences satisfy
p 5 3, and the number of valences with p = 3 is divisible by
4, can have no covering.   0. Ore (New Haven, Conn.)

Waither, H.                             70
Ein kubischer, planarer, zyklisch fiinffach zusammen-
hlngender Graph, der keinen Hamiltonkreis besitzt.
Wiss. 2. Techn. Hochsch. Ilmenau 11 (1965), 163-166.
=\ graph is called cyclically n-connected if at least n edges
must be deleted in order to separate it into two disjoint
parts each of which contains a polygon. It is known that
there exist cyclically 3connected and cyclically 4-con-
netted planar trivalent graphs which are non-Hamiltonian.
The author constructs a cyclically &connected non-
Hamiltonian planar trivalent graph.
             W. T. Tutte (Waterloo, Ont.)

Harary, Frank'; Palmer, Ed
The number of graphs rooted at an oriented line.
ICC Bull. 4 (1965), 91-98.

71

Let G be a graph with p points and let H be an induced
(possibly oriented) subgraph of G with n points (i.e., a
(possibly oriented) subgraph which contains all lines of G
joining a pair of points in H). None of the lines in the
graph G-H is oriented. Let h,, be the number (up to
isomorphism) of such graphs G with p points and q
unoriented lines. The generating function for these graphs
is defined as H,(x) = x4 hpqxq, where q goes from 0 to
(pz -n) + n( p - n). The main result of the paper is a
formula for computing H,(x).

Specifically, HP(x) = Z(I'(H) 0 SP-,,, 1 +z), where r(H)
is the automorphism group of the -oriented graph H,
S, -,, is the symmetric group of degree p - 12, and Z( +) is
the cycle index of (. ),  Leonard Weiss (Providence, R.I.)

Harary, Frank; Palmer, Ed                   72
Enumeration of ~~li:;et graphs,
Proc. Amer. Math. Sot. 17 (1966), 682-687.
A mixed graph is defined as a graph whose edges may be
oriented or nonoriented. The problem is to derive an
expression for the number 7npq, of mixed graphs on p