nLab
category of simple graphs and some graph theory

Graph theory studies both full and wide subcategories of the category SimpGph defined in category of simple graphs. (Needless to say, other categories of graphs have and will be used, but this page focuses on SimpGph.)

Wide subcategories

Definition gives three examples of wide subcategories, the definitons being graph-theoretic, the names immediately chosen to be category-theoretic, for systematic reasons.

Definition

Let MonoSimpGph, RegMonoSimpGph, and IsomeRegMonoSimpGph be the wide subcategories of SimpGph with the following hom-sets:

MonoSimpGph(G 0,G 1G_0,G_1) :=:= {\{ ff \in SimpGph(G 0,G 1)(G_0,G_1): the function ff is injective }\},

RegMonoSimpGph(G 0,G 1G_0,G_1) :=:= {\{ ff \in SimpGph(G 0,G 1)(G_0,G_1): ff is a graph-isomorphism onto its image }\},

IsomeRegMonoSimpGph(G 0,G 1G_0,G_1) :=:= {\{ ff \in SimpGph(G 0,G 1)(G_0,G_1): ff is a graph-isomorphism onto its image, and, for any x,yVx,y\in V we have dist im(f)(f(x),f(y))=dist G 1(f(x),f(y))}\mathrm{dist}_{\mathrm{im}(f)}(f(x),f(y))=\mathrm{dist}_{G_1}(f(x),f(y))\}.

(Here dist G:V×Vω\mathrm{dist}_G\colon V\times V\rightarrow\omega denotes the function which takes any pair of vertices to the length of a shortest graph-theoretic path with these endpoints.)

Closedness under composition of each of the three subclasses of Mor(SimpGph)\mathrm{Mor}(SimpGph) defined by Definition is immediate from the respective definitions.

Evident remarks:

  • Each of MonoSimpGph, RegMonoSimpGph, IsomeRegMonoSimpGph are concrete categories. (because of Proposition )

  • There are the class inclusions (of which the first would be false for multigraphs),

Mor(IsomeRegMonoSimpGph) \subset Mor(RegMonoSimpGph) \subset Mor(MonoSimpGph) == Monos(SimpGph).

  • Because of the latter equality, each of MonoSimpGph, RegMonoSimpGph, IsomeRegMonoSimpGph is a left cancellative category. (And none is a groupoid or a preorder.)

  • None of MonoSimpGph, RegMonoSimpGph, IsomeRegMonoSimpGph has any terminal object.

  • The relation (,)(\emptyset,\emptyset), which is symmetric and reflexive, is the (only) initial object of each of MonoSimpGph, RegMonoSimpGph, IsomeRegMonoSimpGph, because this is the only initial object of SimpGph.

We now explain the names of the three subcategories.

  • It is evident (using the functor Γ\Gamma from the Proposition here that the morphisms of Simp.Gph.Monos are indeed precisely the monos of SimpGph.

  • How to get from the definition of RegMonoSimpGph given in Definition to regular monomorphisms? Answer: directly by definition of graph-isomorphism, Definition says that the morphisms ff of RegMonoSimpGph are those for which the vertex-set im(Γ(f))\mathrm{im}(\Gamma(f)), with Γ\Gamma from Proposition , induces a graph isomorphic to the graph dom(f)\mathrm{dom}(f). Therefore, these morphisms are those injective graph homomorphisms whose image is an induced subgraph of the target. Further, the term used in the nLab instead of induced is full, so the question reduces to why the morphisms ff of SimpGphSimpGph with the two properties that (1) Γ(f)\Gamma(f) is injective and (2) the graph im(f)im(f) is a full subgraph of cod(f)\mathrm{cod}(f), are the regular monos; but sufficient explanations for this have already been given in Section “Equalizers and coequalizers” of category of simple graphs.

  • By definition of IsomeRegMonoSimpGph, for each morphism of that subcategory, the graph im(ff) is what in graph theory usually is called an isometric subgraph.

Isometric subgraphs have several uses in graph-theoretical considerations, which to describe here would take us too far afield.

References

  • Hans-Jürgen Bandelt, Victor Chepoi?, Metric graph theory and geometry: a survey. Contemporary Mathematics, Volume 453, 2008,

Last revised on June 17, 2017 at 09:48:45. See the history of this page for a list of all contributions to it.