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

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 ?

-
Why do you say $R^4$ ? –  Will Jagy Oct 15 '10 at 21:50
You get a grpah which is what is left over when you take the complete bipartite graph K_{n,n} and remove a perfect matching. I think it is nice to observe the cube when n is 4. For other n, I do not expect anything as naturally geometric as the cube. Gerhard "Ask Me About System Design" Paseman, 2010.10.15 –  Gerhard Paseman Oct 15 '10 at 21:54
Will: I imagine R^4 is one way to eliminate any possibility of knots and still use continuous motions to re-form the graph. Gerhard "Ask Me About System Design" Paseman, 2010.10.15 –  Gerhard Paseman Oct 15 '10 at 21:57
So, to rephrase: is there a nice family of polyhedra whose skeletons are the crown graphs ($K_{n, n}$ minus a matching)? –  JBL Oct 15 '10 at 22:23
The skeleton of a polyhedron should be a planar graph, yes? But $K_{6,6}$ minus a matching still contains an induced $K_{3,3}$. –  Ross Churchley Oct 15 '10 at 22:45

These are the crown graphs.

-
Well, the name makes sense, at least. –  drvitek Oct 16 '10 at 5:26

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.

-
So you mean that the adjacent condition on the product is an logical "and" on the product of the adjacent condition on the individual graphs. That makes sense. –  Dany Majard Oct 15 '10 at 22:52
Abosolutely. In particular, it ensures that both projections $\pi_1: G\times H\rightarrow G$ and $\pi_2: G\times H\rightarrow H$ are graph homomorphisms. (A graph homomorphism, by the way, is an adjacency-preserving function $f$ between graphs: i.e. if $uv$ are adjacent, then $f(u)f(v)$ should be adjacent.) –  Ross Churchley Oct 15 '10 at 23:16

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.)

-