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.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
|
||||||||||||||||||||||||
|
|
8
|
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. |
|||||||||||
|
