Contemporary Mathematics

Volume 111, 1990

A Note on Hamilton Cycles in

Block-Intersection Graphs

BRIAN ALSPACH, KATHERINE HEINRICH, AND BOJAN MOHAR

ABSTRACT. We show that the block-intersection graph of a pairwise balanced

design has a Hamilton cycle provided that the cardinality of a largest block

in the design is no more than twice the cardinality of a smallest block.

A set V

= {

1, 2, ... , n} together with a collection B

=

{B

1

, ••• ,

Bm} of

subsets of V is called an incidence structure. The elements of B are called

blocks and the size of a block is the number of elements in it. Let B be an

incidence structure. The block intersection graph of B , denoted G(B) , has

the blocks of B for its vertices and two vertices are adjacent if and only if

the blocks have non-empty intersection.

ExAMPLEs: (i) Let G be a graph. Letting the vertices of G be the elements

of V and the edges of G be the blocks, G determines an incidence structure

B . The block intersection graph of B is then the ordinary line graph of G .

C. Thomassen has conjectured that every 4-connected line graph has a Hamil-

ton cycle.

(ii) Let B be a Steiner triple system. At a regional meeting of the Ameri-

can Mathematical Society in March 1987, R. L. Graham asked if the block-

intersection graph of a Steiner triple system has a Hamilton cycle. This

question is answered in the affirmative in

[1]

and is a corollary of the main

result in this paper.

Let B be an incidence structure on a set V . Define M(B) to be the

multigraph with vertex-set V such that for each pair of distinct vertices a

and b, there is an edge between

a

and b of color Bi if

{a,

b} is a subset

of Bi for Bi

E

B.

1980 Mathematics Subject Classification ( 1985 Revision). Primary 05C38, 05C45; Secondary

05805, 05807.

This research was partially supported by the Natural Sciences and Engineering Research

Council of Canada under Grants A-4792 and A-7829.

This paper is in final form and no version of it will be submitted for publication elsewhere.

©

1990 American Mathematical Society

0271-4132/90 $1.00

+

$.25 per page

http://dx.doi.org/10.1090/conm/111/1079733