Cycles in graphs II
Organizer and Chair: David Gunderson
(University of Manitoba) and Ortrud Oellermann
(University of Winnipeg)
- ARTHUR S. FINBOW, Saint Marys University
Well-Covered Pentagonalizations of the Plane [PDF]
Joint work with B. L. Hartnell and Michael D. Plummer.
A graph is said to be well-covered if every maximal independent set of vertices has the
same cardinality. A planar (simple) graph in which each face is bounded by a pentagon is
called a (planar) pentagonalization.
In this Talk, we investigate those planar pentagonalizations which are well-covered.
keywords: independent set, well-covered, pentagonalization
- SHONDA GOSSELIN, University of Winnipeg
Cyclic hypergraph decompositions [PDF]
We examine edge decompositions of complete uniform hypergraphs whose parts are permuted transitively by a permutation of the vertex set. We present an algebraic method for constructing such a hypergraph decomposition which is related to the well known Paley graph construction. The construction is derived from a partition of the cosets of a group and a function from the power set of the vertex set into this group. Several examples will be constructed using different groups and we discuss the symmetry and other properties of the hypergraphs in the decompositions we obtain.
- JOY MORRIS, University of Lethbridge
Colour-preserving and colour-permuting automorphisms [PDF]
The connection set of a Cayley graph yields a natural colouring/cycle decomposition of the graph if the group has odd order, and may include some 1-factors if the group has even order.
We consider groups and connected Cayley graphs for which the colour-preserving or colour-permuting graph automorphisms all come from the group structure, i.e. are also automorphisms of the group, and those for which this is not true. For circulant graphs, we show that even if each cycle in this decomposition is given a unique colour, the only graph automorphisms that permute these colours are group automorphisms.
- MICHAEL PLUMMER, Vanderbilt University, Nashville, TN USA
Distance matching in punctured planar triangulations [PDF]
Distance matching extension with prescribed and proscribed edges in planar triangulations has been previously studied. In the present work, matching extension behavior is investigated when the graph families are slightly more general than triangulations. More particularly, we replace the triangulation hypothesis with weaker hypotheses that (a) the graph is locally connected and (b) the graph has at most two non-triangular faces. We investigate which distance matching properties enjoyed by triangulations are retained and which are lost.
This is joint work with Robert Aldred.