Wealhon ation! Karras

Ope AGU]
COMBINATORIAL ANALYSIS

| to j.) The unique polynomial of least degree satisfying

cycles; if there are no cycles or if all cycles have pseudo-

length 0, then the index is taken to be 0. Typical results: -

(1) Ifin 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
some clirected edge, then the number of connected com-
ponents of the graph @ x H is the greatest common divisor
of the index of G and the index of H. The seconc result
was obtained earlier for strongly connected oriented
graphs by McAndrew [Proc. Amer. Math. Soc. 14 (1963),
600-606; MR 27 #1932]. G. N. Raney (Storrs, Conn.)

Halin, Rudolf 65
Graphen ohne unendliche Wege.
Math. 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. 7. Tutte (Waterloo, Ont.)

Harary, Frank; Nash-Williams, C. St. J. A. 66
On eulerian and hamiltonian graphs and line graphs.
Canad. Math. Bull. 8 (1965), 701-709.

The line graph L(G) is the incidence graph of the edges of

G, Additional graphs Z,(@) (n2 2) are defined, and some

relationships between Eulerian and Hamiltonian proper-

ties of G, L(G), and the graphs Z,(@) are found. {The

reader may find it helpful to note that L,(@)= L(M,(G@)),

where 4,(@) is the graph obtained from G by replacing

each edge of G by a path consisting of n edges; thus L,

is not the ath iterate of Z.}

D. W. Walkup (Seattle, Wash.)

Havel, ivan 67
Cn the completeness-number of a finite graph. (Czech
and Russian summaries)

Casopis Pést. 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 @’ 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 @"’. W. T. Tutte (Waterloo, Ont.)

Hoffman, A. J.; McAndrew, M. H. 68
Tne polynomial of a directed graph.
Proc. Amer. Math. Soc. 16 (1965), 303-309.
Let G be a directed graph and A the adjacency matrix of
G. It is proved that there exists a polynomial P(x) such
that P(A)=J (when J is the matrix consisting entirely of

l’s) if and only if @ is strongly connected and strongly }

regular. (G is strongly regular if for each vertex 7 the
number of edges with initial vertex 7 equais the number of
edges with terminal vertex 7; @ is strongly connected if
for any vertices 1,7 (¢#j), there is a directed path from 7

 

65-72

P(A) =Jd (called the polynomial belonging to G) is charac-
terized 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 ¢ be a positive integer and let
G, be the graph whose vertices are all ordered pairs (1, 7)
of residues mod ¢ and whose edges go from (#, j) to (t, j +1)
and (i+1,j) for all i,j. Let P,(z) be the polynomial
belonging to G,. The following theorem is proved: If¢ is a
prime or {= 4 and if H is a graph with ¢? vertices such that
P,(x) belongs to H, then H = G,.

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

Troy, D. J. 69
On traversing graphs.
Amer. Math. Monthly 73 (1966), 497-499.
A covering of a graph G is a eyclic 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 <3, and the number of valences with p=3 is divisible by
4, can have no covering. O. Ore (New Haven, Conn.)

 

Waither, H. 70
Ein kubischer, planarer, zyklisch fiinffach zusammen-
hingender Graph, der keinen Hamiltonkreis besitzt.
Wiss. Z. Techn. Hochsch. Ilmenau 11 (1965), 163-166.

A 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 3-connected and cyclically 4-con-
nected planar trivalent graphs which are non-Hamiltonian.

The author constructs a cyclically 5-connected non-

Hamiltonian planar trivalent graph.

W. T. Tutte (Waterloo, Ont.)

—

 

 

Harary, Frank; Palmer, Ed 71

The number of graphs rooted at an oriented line.

ICC Bull. 4 (1965), 91-98.

Let G be a graph with p points and let H be an induced
(possibly oriented) subgraph of G with x 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 4,, 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)= >, hygt?, where g goes from 0 to
(pg—n)+n(p—n). The main result of the paper is a
formula for computing H,(z).

Specifically, H,(x)=Z(I'(H) ° S,-,,1+), where P(H)
is the automorphism group of the oriented graph 4H,
S,-, is the symmetric group of degree p—n, and Z(-) is
the cycle index of (-). Leonard Weiss (Providence, R.I.)

Harary, Frank; Palmer, Ed 72
Enumeration of mixec graphs.
Proc. Amer. Math. Soc. 27 (1968), 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 m,,, of mixed graphs on p

tt