3
$\begingroup$

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 ?

$\endgroup$
7
  • $\begingroup$ Why do you say $R^4$ ? $\endgroup$
    – Will Jagy
    Oct 15, 2010 at 21:50
  • $\begingroup$ 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 $\endgroup$ Oct 15, 2010 at 21:54
  • $\begingroup$ 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 $\endgroup$ Oct 15, 2010 at 21:57
  • $\begingroup$ So, to rephrase: is there a nice family of polyhedra whose skeletons are the crown graphs ($K_{n, n}$ minus a matching)? $\endgroup$
    – JBL
    Oct 15, 2010 at 22:23
  • 1
    $\begingroup$ 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}$. $\endgroup$ Oct 15, 2010 at 22:45

2 Answers 2

4
$\begingroup$

These are the crown graphs.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 15, 2010 at 22:52
  • $\begingroup$ 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.) $\endgroup$ Oct 15, 2010 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.