Spelling suggestions: "subject:"ld5655.v856 1982.585"" "subject:"ld5655.v856 1982.1585""
1 |
Circularity of graphsBlum, Dorothee Jane January 1982 (has links)
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)→Z<sub>n</sub>}. 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)→Z<sub>n</sub> is a co-admissible map, then G contains a cycle, J, called a co-admissible cycle, for which g:V(J)→Z<sub>n</sub> 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 Z<sub>r</sub> or every vertex of P with valency two induces exactly two elements of Z<sub>r</sub> not induced by any other vertex of G. Finally it is shown that if G is a planar graph and if g:V(G)→Z<sub>n</sub> is a co-admissible map, then any planar representation of G has exactly two faces bounded by co-admissible cycles. / Doctor of Philosophy
|
Page generated in 0.0461 seconds