Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-23T02:13:58.333Z Has data issue: false hasContentIssue false

Double covers of graphs

Published online by Cambridge University Press:  17 April 2009

Derek A. Waller
Affiliation:
Department of Pure Mathematics, University College, Swansea, Wales.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A projection morphism ρ: G1G2 of finite graphs maps the vertex-set of G1 onto the vertex-set of G2, and preserves adjacency. As an example, if each vertex v of the dodecahedron graph D is identified with its unique antipodal vertex (which has distance 5 from v) then this induces an identification of antipodal pairs of edges, and gives a (2:1)-projection p: D → P where P is the Petersen graph.

In this paper a category-theoretical approach to graphs is used to define and study such double cover projections. An upper bound is found for the number of distinct double covers ρ: G1G2 for a given graph G2. A classification theorem for double cover projections is obtained, and it is shown that the n–dimensional octahedron graph K2,2,…,2 plays the role of universal object.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1976

References

[1]Biggs, Norman, Algebraic graph theory (Cambridge Tracts in Mathematics, 67. Cambridge University Press, Cambridge, 1974).Google Scholar
[2]Djoković, D.Ž., “Automorphisms of graphs and coverings”, J. Combinatorial Theory Ser. B 16 (1974), 243247.Google Scholar
[3]Farzan, M. and Waller, D.A., “Kronecker products and local joins of graphs”, submitted.Google Scholar
[4]Gardiner, A., “Antipodal covering graphs”, J. Combinatorial Theory Ser. B 16 (1974), 255273.Google Scholar
[5]Harary, Frank, Graph theory (Addison-Wesley, Reading, Massachusetts; London; Ontario; 1969).Google Scholar
[6]Husemoller, Dale, Fibre bundles (McGraw-Hill, New York, St. Louis, San Francisco, Toronto, London, Sydney, 1966).Google Scholar
[7]Massey, William S., Algebraic topology: an introduction (Harcourt, Brace and World, New York, 1967).Google Scholar
[8]Smith, D.H., “Primitive and imprimitive graphs”, Quart. J. Math. Oxford Ser. 22 (1971), 551557.Google Scholar