The University of Montana
Department of Mathematical Sciences

Technical report #9/2012

On the Concrete Categories of Graphs

George McRae
University of Montana

Demitri Plessas
University of Montana

Liam Rafferty
University of Montana

Abstract

In the standard Category of Graphs, the graphs allow only one edge to be incident to any two vertices, not necessarily distinct, and the graph morphisms must map edges to edges and vertices to vertices while preserving incidence. We refer to these graph morphisms as Strict Morphisms. We relax the condition on the graphs allowing any number of edges to be incident to any two vertices, as well as relaxing the condition on graph morphisms by allowing edges to be mapped to vertices, provided that incidence is still preserved. We call this broader graph category The Category of Conceptual Graphs, and define four other graph categories created by combinations of restrictions of the graph morphisms as well as restrictions on the allowed graphs.

We investigate which Lawvere axioms for the category of Sets and Functions apply to each of these Categories of Graphs, as well as the other categorial constructions of free objects, projective objects, generators, and their categorial duals.

Keywords: graph morphisms, graph homomorphisms, concrete categories, cartesian closed category, topos, Categories of Graphs

AMS Subject Classification: Primary: 18B99, Secondary: 05C25, 18A40, 18D15

Download Technical Report: Pdf (535 KB)