# Graph with group structure?

Is there any established theory of graphs which themselves are groups? I don't mean Cayley graphs or "graphs of groups". I mean a graph whose set of vertices forms a group, where the group operation is compatible with the graph structure in some way. Like for example any two adjacent vertices have adjacent inverses, and some similar adjacency condition for the multiplication operation.

Simple cycles would have this property, though I'm not sure what else. Is there a name for this? Hard to google due to many similar concepts.

• What do you mean by "some similar adjacency condition for the multiplication operation"? -- Probably not "the product of two adjacent vertices is adjacent to itself, i.e. carries a loop"(?) – Stefan Kohl Oct 15 '15 at 17:21
• @StefanKohl- I'm not sure exactly. Maybe something like: if $x,y,x',y'$ are vertices with $x,x'$ adjacent and $y,y'$ adjacent, then $xy$ and $x'y'$ are adjacent (or perhaps equal). EDIT- that's probably not what i want. How about just- for any $x$, if $y$ and $y'$ are adjacent, then $xy$ and $xy'$ are adjacent. I don't think this is equivalent to what I said before. – Chris Oct 15 '15 at 17:25
• Do you just want a graph with a group action that is regular on the set of vertices, then? – Jeremy Rickard Oct 15 '15 at 17:30
• @JeremyRickard- yes I think that's what I want. Are there interesting examples of such graphs? – Chris Oct 15 '15 at 17:54
• Well, that's pretty much a Cayley graph (if you don't require the graph to be connected then it might be a "Cayley graph" with respect to a set of elements that don't generate the group). – Jeremy Rickard Oct 15 '15 at 18:39

I can at least propose a definition. To my mind, the categorically best behaved category of graphs is the category of presheaves on $\{ \bullet \rightrightarrows \bullet \}$ ("directed multigraphs"); explicitly, it's the category of tuples $(E, V, s, t)$ of an edge set $E$, a vertex set $V$, and two functions $s, t : E \to V$ (the source and target of an edge). Among other things, this is the category over which the category of small categories is monadic. So:

Proposal: A "group graph" is a group object in the category of graphs (in the above sense).

Explicitly, a group graph is a tuple $(E, V, s, t)$ of two groups $E, V$ (so edges admit a multiplication too, not just vertices) and two group homomorphisms $s, t : E \to V$. Note that this is the same thing as a graph object in the category of groups, and that another way to say "graph object" is "coequalizer diagram."

Said another way, first we need a group operation $\otimes$ on vertices, and then given two edges $e_1 : s_1 \to t_1, e_2 : s_2 \to t_2$, they admit a product which takes the form $e_1 \otimes e_2 : s_1 \otimes s_2 \to t_1 \otimes t_2$, and this product also satisfies the group axioms.

Example. Given any homomorphism $f : G \to H$ of groups, taking its kernel pair gives a diagram

$$G \times_H G \rightrightarrows G \to H$$

and the first part $G \times_H G \rightrightarrows G$ of this diagram (where the two morphisms are the two projections) is naturally a graph object. This construction generalizes to any category with pullbacks.

A related but more familiar thing you could ask for is a "group object" in categories rather than graphs; that is, a monoidal category in which every object is invertible (this is the motivation for the notation $\otimes$). This notion and various related notions are important in algebraic topology and other fields which make use of higher category theory; compare the notion of 2-group and "Picard groupoid."

Another related but more familiar thing you could ask for is a simplicial group (thinking of graphs as being like simplicial sets, but over a truncated version of the simplex category).

• Other nice categories of graphs in which it would be viable to develop internal group theory include the category of sets equipped with a relation satisfying a subset of the properties {reflexivity, symmetry}. Each of the four possible such categories is a Grothendieck quasitopos, making them almost as categorically nice as the topos of directed multigraphs, and closer to what graph theorists typically mean by "graph". – Todd Trimble Oct 15 '15 at 18:55