• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Circularity of graphs

Blum, 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.0303 seconds