On a special kind of graph connectig n point to n points. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T20:04:34Z http://mathoverflow.net/feeds/question/42332 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42332/on-a-special-kind-of-graph-connectig-n-point-to-n-points On a special kind of graph connectig n point to n points. Dany Majard 2010-10-15T21:42:25Z 2010-10-16T02:38:09Z <p>I don't know anything about graph theory and I was wondering about something :</p> <p>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 ?</p> <p>n=2 gives two lines</p> <p>n=3 gives a hexagon</p> <p>n=4 gives a cube</p> <p>n=5 ...</p> <p>Is there a general object class apart the one described just the way I did ?</p> http://mathoverflow.net/questions/42332/on-a-special-kind-of-graph-connectig-n-point-to-n-points/42335#42335 Answer by Ross Churchley for On a special kind of graph connectig n point to n points. Ross Churchley 2010-10-15T22:36:51Z 2010-10-15T22:36:51Z <p>Let $G$ and $H$ be graphs. The graph $G\times H$, called the <a href="http://en.wikipedia.org/wiki/Tensor_product_of_graphs" rel="nofollow"><em>tensor</em>, <em>direct</em> or <em>categorical product</em></a> 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$. </p> <p>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.</p> <p>The categorical product is an incredibly useful (and well-studied) concept in the study of graph homomorphisms. Chapter 2 of <em><a href="http://www.cs.sfu.ca/~pavol/hombook.html" rel="nofollow">Graphs and Homomorphisms</a></em> 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 <em>Product Graphs: Structure and Recognition</em> has more on them.</p> http://mathoverflow.net/questions/42332/on-a-special-kind-of-graph-connectig-n-point-to-n-points/42357#42357 Answer by drvitek for On a special kind of graph connectig n point to n points. drvitek 2010-10-16T02:03:53Z 2010-10-16T02:03:53Z <p>Ross's answer is more helpful in terms of structure, but I will point out that your graph is also an example of a <em>circulant graph</em>. Informally, a circulant graph is defined by parameters $n$ and $v$, with $v$ a vector in <code>$\mathbb{N}^m\;(m&lt;n)$</code>. 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)$.</p> <p>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.)</p> http://mathoverflow.net/questions/42332/on-a-special-kind-of-graph-connectig-n-point-to-n-points/42358#42358 Answer by David Eppstein for On a special kind of graph connectig n point to n points. David Eppstein 2010-10-16T02:38:09Z 2010-10-16T02:38:09Z <p>These are the <a href="http://en.wikipedia.org/wiki/Crown_graph" rel="nofollow">crown graphs</a>.</p>