- Go to Abstract
- Abstract in PDF
- Dissertation in a single PDF file
- Dissertation in smaller PDF files
- Cover and Introduction (pages 1-9)
- Chapter 1. A LOWER BOUND FOR SNAKE-IN-THE-BOX CODES (pages 10-28)
- Chapter 2. ON SMALL GRAPHS WITH HIGHLY IMPERFECT POWERS (pages 29-49)
- Chapter 3. EQUITABLE LABELLINGS OF CYCLES (pages 50-68)
- Chapter 4. SPLITTING NECKLACES AND A GENERALIZATION OF THE BORSUK-ULAM ANTIPODAL THEOREM (pages 69-93)
- Chapter 5. REMARKS ON A GENERALIZATION OF RADON’S THEOREM (pages 94-97)
- Chapter 6. AN OBSERVATION ON INTERSECTION DIGRAPHS OF CONVEX SETS IN THE PLANE (pages 98-100)
- References (pages 101-104)

Doctor of Philosophy

of the University of Cambridge

April 1990

Supervised by Dr. Béla Bollobás

The first problem we deal with in this dissertation concerns long induced cycles in the d-dimensional cube, i.e. the graph on d-tuples of binary digits with pairs of vertices differing in exactly one coordinate as edges. Such cycles were introduced by Kautz as a type of error-checking codes (called the snake-in-the-box codes) for a certain analogue-to-digital conversion system. We give a simple and very natural construction of such a cycle whose length is given by a linear function of the number of vertices of the cube. This construction improves a previous construction given by Danzer and Klee.

Next we turn our attention to a certain generalization of the chromatic number
of graphs. Given a natural number s, we denote by c_{s}(G) the minimal
number of colours needed to colour the vertices of G in such a way that any
pair of vertices of the same colour is at a distance greater than s. We give
a construction of a family of graphs G for which the gap between c_{s}(G)
and the largest subgraph of G of diameter at most s is big in terms of the
number of vertices of G. This construction allows us to improve previous
results of Gionfriddo and Milici.

As the next problem we consider a question about the possibility of colouring
cycles in a special way. The colourings in question are called the minimally
k-equitable labellings and are analogous to the graceful labellings
introduced in connection with the longstanding Ringel-Kotzig conjecture. A
labelling of the vertices of a graph G is minimally k-equitable if the
labels are distinct positive natural numbers not exceeding the number of
vertices of G, and in the partition of the set of edges of G according to
the absolute value of the difference of the labels of their end-points, all the
sets have cardinality k. We settle Bloom's question of whether all cycles
C_{mk}, where m,k > 1, have minimally k-equitable labellings.

Another problem we deal with concerns `opened' coloured cycles, i.e. coloured paths. Assume that we want to cut a small number of edges of a t-coloured path in such a way that the segments we get can be used to partition the set of vertices of the path into k subsets which have the property that every colour is represented by the same number of vertices in any element of the partition. We are interested in an upper bound for the number of such cutpoints in terms of t and k, and give a new proof of the bound t(k-1) conjectured by Alon and West which was later proved by Alon.

Two other minor results are also given in the dissertation; one concerns a
generalization of Radon's theorem about convex hulls of finite sets in R^{n}, and the other a problem posed by West about intersection digraphs of
convex sets in the plane.

Home Top