-1
$\begingroup$

I am interested in the intersection graphs of $\binom{X}{2}$, i.e. the set of all 2-element subsets of a (finite) set $X$.

[Motivation: One can represent every simple graph with $n$ vertices by an assignment of 0 or 1 to the vertices of the intersection graph of $\binom{[n]}{2}$. This is a somehow more "natural" (= "coordinate free") representation of a graph than the usual adjacency matrix.]

Especially I wonder

  • In which (other) contexts are/were these graphs investigated?

  • How can they be characterized abstractly?

  • And do they have a name, thus being characterized?

Improve this question
$\endgroup$
5
  • $\begingroup$ What's unnatural about the adjacency matrix? Regarded as an operator $\mathbb{R}^V \to \mathbb{R}^V$ it's perfectly coordinate-free. $\endgroup$
    – Qiaochu Yuan
    Commented May 29, 2013 at 8:33
  • 1
    $\begingroup$ The complement is a Kneser graph. en.wikipedia.org/wiki/Kneser_graph $\endgroup$
    – Ben Barber
    Commented May 29, 2013 at 8:40
  • $\begingroup$ What is $\mathbb{R}^V$ supposed to be? (I always regarded the adjancency matrix as a function $[n]^2 \rightarrow \lbrace 0,1\rbrace$.) $\endgroup$
    – Hans-Peter Stricker
    Commented May 29, 2013 at 8:57
  • $\begingroup$ @Butch: I'll provide a labelled picture. And I've been wrong about the neighbours forming a cycle, so I deleted that part of my question. $\endgroup$
    – Hans-Peter Stricker
    Commented May 29, 2013 at 9:15
  • $\begingroup$ @Qiaochu: Googling for "adjacency matrix operator" I found this: math.stackexchange.com/questions/270058/…. Thanks! $\endgroup$
    – Hans-Peter Stricker
    Commented May 29, 2013 at 9:53

1 Answer 1

Reset to default
5
$\begingroup$

The usual name of your graph is $L(K_n)$, the line graph of the complete graph $K_n$. The line graphs of complete graphs have also been called triangular graphs, as I just learned moments ago from the Wikipedia article http://en.wikipedia.org/wiki/Line_graph .

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .