On a special kind of graph connectig n point to n points. - MathOverflow

On a special kind of graph connectig n point to n points.

2010-10-15T21:42:25Z

I don't know anything about graph theory and I was wondering about something :

If you draw two parallel rows of n points in $\mathbb R^4$ and link each point with all the points in the opposite row except the one right in front of it, and then allow the points to move where ever, what do you get ?

n=2 gives two lines

n=3 gives a hexagon

n=4 gives a cube

n=5 ...

Is there a general object class apart the one described just the way I did ?

Answer by Ross Churchley for On a special kind of graph connectig n point to n points.

2010-10-15T22:36:51Z

Let $G$ and $H$ be graphs. The graph $G\times H$, called the tensor, direct or categorical product of $G$ and $H$, has vertices $V(G\times H)=V(G)\times V(H)$, and has an edge between $(u, v)$ and $(u', v')$ whenever $u$ is adjacent to $u'$ in $G$ and $v$ is adjacent to $v'$ in $H$.

I believe you're describing the product $K_2\times K_n$. If we label each vertex by a pair $(i, j)$ where vertices in the same "parallel row" are assigned the same $i$, and vertices "in front of" each other are assigned the same $j$, then your description says that two vertices $(i, j)$ and $(i', j')$ are adjacent if and only if $i\not=i'$ or $j\not=j'$. Since two vertices in a complete graph are adjacent if and only if they are distinct, this is just the same adjacency conditions as in the definition above.

The categorical product is an incredibly useful (and well-studied) concept in the study of graph homomorphisms. Chapter 2 of Graphs and Homomorphisms collects a number of results relating to this product. There are many other product operations defined for graphs, which are useful in other contexts; I believe the book Product Graphs: Structure and Recognition has more on them.

Answer by drvitek for On a special kind of graph connectig n point to n points.

2010-10-16T02:03:53Z

Ross's answer is more helpful in terms of structure, but I will point out that your graph is also an example of a circulant graph. Informally, a circulant graph is defined by parameters $n$ and $v$, with $v$ a vector in $\mathbb{N}^m\;(m<n)$ . One takes the empty graph on $n$ vertices labeled $1, 2, \cdots, n$, and joins vertex $i$ to vertices $i + v_1, i+v_2, \cdots, i+v_m$ (reduced modulo $n$). So for example the complete graph on three vertices has $n = 3$ and $v = (1,2)$.

Your case is the circulant graph on $2n$ vertices with vector $v = (3,5,\cdots,2n-1)$. (There are lots of other vectors $v$ which give isomorphic graphs, but this one is the easiest to see why it works.)

Answer by David Eppstein for On a special kind of graph connectig n point to n points.

2010-10-16T02:38:09Z

These are the crown graphs.