Circularity of graphs

Abstract

Let G be a finite connected graph. The circularity of G has been previously defined as σ(G) = max{r ε N| G has a circular covering of r elements, each element being a closed, connected subset of G containing at least one vertex of G}. This definition is known to be equivalent to the combinatorial description, σ(G) = max{r ε N| there is an admissible map f:V(G)→A(r)}. In this thesis, co-admissible maps are introduced and the co-circularity of a graph, G, is defined as η(G) = max{n ε N| there is a co-admissible map g:V(G)→Zn}. It is shown that σ(G) = 2η(G) or 2η(G) + 1. It is also shown that if G is a graph and g:V(G)→Zn is a co-admissible map, then G contains a cycle, J, called a co-admissible cycle, for which g:V(J)→Zn is also co-admissible. Necessary and sufficient conditions are given for extending a co-admissible map on a cycle of a graph to the entire graph. If G is a graph with σ(G) = r, it is shown that any suspended (v,w)-path P in G induces, under any admissible map f:V(G)→A(r), either at most four elements of Zr or every vertex of P with valency two induces exactly two elements of Zr not induced by any other vertex of G. Finally it is shown that if G is a planar graph and if g:V(G)→Zn is a co-admissible map, then any planar representation of G has exactly two faces bounded by co-admissible cycles.