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.
7
-
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$– Chris GodsilCommented 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$– André HenriquesCommented 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$– André HenriquesCommented Jun 9, 2012 at 19:11
-
1$\begingroup$ I am interested in finding the chromatic number of this graph. $\endgroup$– hbmCommented 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$– Chris GodsilCommented Jun 9, 2012 at 21:45
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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.
Martin Brandenburg
63.1k12 gold badges207 silver badges424 bronze badges
answered Jun 9, 2012 at 19:12
-
1$\begingroup$ I've corrected the link. $\endgroup$ Commented 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$ Commented 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$ Commented Jun 10, 2012 at 2:15