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.

  • 3
    $\begingroup$ 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. $\endgroup$ Jun 9, 2012 at 18:59
  • 4
    $\begingroup$ @Chris: "It does not seem to be a suitable class of graphs for a research project of any kind": that's a bit pretentious... $\endgroup$ Jun 9, 2012 at 19:07
  • $\begingroup$ @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? $\endgroup$ Jun 9, 2012 at 19:11
  • 1
    $\begingroup$ I am interested in finding the chromatic number of this graph. $\endgroup$
    – hbm
    Jun 9, 2012 at 19:34
  • 1
    $\begingroup$ @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? $\endgroup$ Jun 9, 2012 at 21:45

1 Answer 1


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.

  • 1
    $\begingroup$ I've corrected the link. $\endgroup$ Jun 9, 2012 at 19:41
  • $\begingroup$ 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. $\endgroup$ Jun 9, 2012 at 21:49
  • $\begingroup$ As I said: complete DIRECTED graph plus self edges... But yes, the undirected bipartite graph works also. $\endgroup$ Jun 10, 2012 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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