4
$\begingroup$

Given a graph $G=(E,V)$, I construct a graph $G'$ where the vertices of $G'$ are given by the edges of $G$ and say that two edges of $G$ are neighbors in $G'$ if they have a common vertex.

Is there a standard terminology for this construction, please? Is there a book/an article with all the standard properties of these graphs?

I thank you much in advance.

$\endgroup$
1
  • 8
    $\begingroup$ I do not think that the question is illegitimate in MO: someone who is not from the domain need not know the terminology, and this kind of questions are really difficult to answer alone using Google and the like, while they are easy to answer in MO. I think the best would be for Casteels to post his or her comment as an answer, and for sylvain g to accept it so that the question is officially considered answered. $\endgroup$ Dec 2, 2014 at 15:03

2 Answers 2

6
$\begingroup$

The standard name for what you are describing is the line graph of $G$, however according to the wikipedia entry, it actually has been called the "edge graph" as well. While the wikipedia article is fairly extensive, you can also find information about line graphs in most graph theory textbooks, with perhaps Harary's book the best place to start (Chapter 8).

$\endgroup$
1
  • $\begingroup$ Line graphs have also been called "interchange graphs", and Wolfram gives a whole bunch of additional synonyms. $\endgroup$
    – bof
    Aug 12, 2017 at 11:45
1
$\begingroup$

Casteels' answer answers well to the first part of the OP (it is particularly nice that Casteels mentions the undeservedly-rare variant term 'edge graph').

Yet I think the following additions should be made:

(0) From a systematizing point of of view (favoring a general-concept-specialized-to-a-context over a term specific-to-the-context; some say top-down instead of bottom-up) neither 'line graph', nor 'edge graph' should be used (in my opinion), rather

intersection graph of $G$

should be used. Here, 'intersection graph of a hypergraph($=$set of sets of a specified set)' is the general concept, which then gets specialized to the context 'graphs conceived of as 2-uniform hypergraphs'.

(1) The second half of the OP, i.e.

Is there a book/an article with all the standard properties of these graphs?

should be answered.

Needless to say, "all the standard properties" is undefined, yet in a reasonably loose sense, 'some standard properties' say, I think the answer is: a book devoted to line graphs only does not exist, yet there is an article: it is a long time that I read it, but I think a recommendable survey dedicated to 'line graphs' is

  • Erich Prisner, Line graphs and generalizations – a survey , in: Surveys in Graph Theory (G. Chartrand, M. Jacobson eds.), Congressus Numerantium 116 (1996) 193–230

Regrettably, it seems not to be available online. (Incidentally, as of writing this, a large search engine, with remarkable consistency, claims that Prisner's survey was published in 'Abh. Math. Sem. Univ. Hamburg', Volume 35; non-existence is hard to prove, yet this seems false in the sense that (0) I did not see loc. cit. in Volum 35 of 'Abh. Math. Sem. Univ. Hamburg', (1) loc. cit. is usually cited to be in 'Congressus Numerantium', (2) I once read a paper coppy of the version of Prisners survey that I recommend here.)

(2) I think if someone apparently not knowing about line graphs asks about them, a brief mention should be made of a famous theorem of L. W. Beineke which is a theorem of the kind non-first-order defined class of structures turns out to be first-order axiomatizable, or even finitely-axiomatizable (in the usual sense of model theory): the most usual definition of 'line graph' involves a quantification over relations: 'there exists a graph($=$symmetric irreflexive binary relation on a set) such that this graph is the line graph of it', and hence is not 'first-order' in any reasonable sense

Yet by Beineke's theorem1 there exists an explicitly known 9-element set $S$ of finite graphs such that any graph $G$ is a 'line graph' if and only if $G$ does not contain any induced subgraph isomorphic to a member of $S$. This shows that the class of 'line graphs' is finitely axiomatizable in the usual one-sorted first-order logic of graphs (with equality, and with one-element signature $\sim$). Beineke's line graph theorem is a gem.

1 Which remarkably, is valid for infinite graphs, or, more precisely, Beineke wisely never mentions the assumption 'finite' anywhere in his original paper, and his proof goes through for arbitrary graphs.

$\endgroup$
1
  • $\begingroup$ Dear @bof: many thanks for catching this: no, $k$-uniform hypergraphs are not called $k$-regular hypergraphs. This was a simple oversight. I will correct it. Thanks again. $\endgroup$ Aug 12, 2017 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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