MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I came across the graph $G= (V, E)$, where

$V =$ { $(i, j)| 1 \leq i, j \leq n$ }

$E=${ $((i, j), (k,l))| i \ne l$ and $j \ne k$ }

Does this graph have a name? Is it well studied?

I would very much like to see some of their properties.

share|cite|improve this question
It's the complement of the Cartesian square of the complete graph on $n$ vertices. It does not seem to be a suitable class of graphs for a research project of any kind. – Chris Godsil Jun 9 '12 at 18:59
@Chris: "It does not seem to be a suitable class of graphs for a research project of any kind": that's a bit pretentious... – André Henriques Jun 9 '12 at 19:07
@hbm: Your question is not motivated... Without more background, I fear that nobody will be able to help you. It would help us if you could tell us what you are looking for? For example, how did you get interested in this particular graph? – André Henriques Jun 9 '12 at 19:11
I am interested in finding the chromatic number of this graph. – hbm Jun 9 '12 at 19:34
@André: As the question is stated I do not think it is a suitable question for this site. There are an awful lot of graphs, and we could pose the same question for many families. Asking about the chromatic number is more focussed, but still some reason for picking on this family should be offered - why should we care? – Chris Godsil Jun 9 '12 at 21:45

I think you just have the complement of a line graph here.

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

The line graph $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$.

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

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.

share|cite|improve this answer
I've corrected the link. – Martin Brandenburg Jun 9 '12 at 19:41
The graph has $n^2$ vertices, its the complement of the line graph of the complete bipartite graph $K_{n,n}$, not of the complete graph. – Chris Godsil Jun 9 '12 at 21:49
As I said: complete DIRECTED graph plus self edges... But yes, the undirected bipartite graph works also. – Vidit Nanda Jun 10 '12 at 2:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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