Circularity of graphs

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_n}. 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_n is a co-admissible map, then G contains a cycle, J, called a co-admissible cycle, for which g:V(J)→Z_n 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_r or every vertex of P with valency two induces exactly two elements of Z_r 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_n is a co-admissible map, then any planar representation of G has exactly two faces bounded by co-admissible cycles.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

doctoral

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1982

Author dc:creator

• Blum, Dorothee Jane

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10919/88719

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/88719