Is this graph known? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T11:28:10Z http://mathoverflow.net/feeds/question/99186 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99186/is-this-graph-known Is this graph known? hbm 2012-06-09T18:03:11Z 2012-06-09T19:41:33Z <p>I came across the graph $G= (V, E)$, where </p> <p>$V =$ { $(i, j)| 1 \leq i, j \leq n$ } </p> <p>$E=${ $((i, j), (k,l))| i \ne l$ and $j \ne k$ }</p> <p>Does this graph have a name? Is it well studied? </p> <p>I would very much like to see some of their properties.</p> http://mathoverflow.net/questions/99186/is-this-graph-known/99188#99188 Answer by Vidit Nanda for Is this graph known? Vidit Nanda 2012-06-09T19:12:35Z 2012-06-09T19:41:33Z <p>I think you just have the complement of a line graph here.</p> <p>Start with $K_n$, the complete directed graph on $n$ vertices (including self-edges). That is, the vertex set is $\lbrace 1,\ldots,n \rbrace$ and you have all possible directed edges $(i,j)$ for vertices $i$ and $j$ including when $i=j$.</p> <p>The <a href="http://en.wikipedia.org/wiki/Edge_graph" rel="nofollow">line graph</a> $LK_n$ of $K_n$ is the undirected graph which has a vertex $v_{ij}$ for each edge $(i,j)$ in $K_n$. Since $K_n$ is complete, you get precisely the vertex set of the graph $G$ from the question. Now as for the edges: there is an edge in $LK_n$ between $v_{ij}$ and $v_{kl}$ if and only if $j=k$.</p> <p>Your graph $G$ is the complement of $LK_n$; that is, it has the same vertex set but an edge between $v_{ij}$ and $v_{kl}$ if and only if there is no edge between these vertices in $LK_n$.</p> <p>As for properties, there is a large amount of information about complete directed graphs, line graphs and graph complements a google search away. Perhaps if you provide context and motivation for how your graph arose and what properties you would be interested in, someone here will point you to appropriate literature.</p>