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)