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
Previous Page Next Page