Re: Undirected graphs

[Sebastiano Vigna <vigna@dsi.unimi.it>]

On Wed, 2006-03-08 at 11:07 -0400, Robert Pare wrote:

> by 1 and 2, or just 2.) Which is nice but what about loops?
> The involution might fix a loop or not. So wouldn't we be
> getting undirected graphs with two kinds of loops, whole loops
> and semiloops? What am I missing?

Yes, you'll get two kind of loops. This explains why in topological
graph theory books sometimes you'll find a remark like "we will count
loops once" or "we will count loops twice" (in the first case, sometimes
loops are depicted as segments going out of vertices with a dashed
ending). The problem is that the standard representation for undirected
graphs (subsets of unordered pairs) fails to distinguish between the two
kind of loops. The presheaf representation makes this distinction
clear.

In most cases you can forget about this problem, but when studying
covering the difference is huge: a loop fixed by the involution is
covered by an edge, whereas a pair of loops exchanged by the involution
are covered by a line. We discussed this issue at some length in our
paper "Fibrations of graphs" (Discrete Math., 2002).

Ciao,

						seba