Talk:Line graph

Untitled

Please convert the AASCI Art graphs to images. Thank you. —Preceding unsigned comment added by 213.211.224.201 (talk • contribs) 11:24, 15 July 2005 (UTC)

hi i dont like it —Preceding unsigned comment added by 216.230.150.7 (talk • contribs) 20:03, 4 June 2006 (UTC)

Why isn't the article isn't complete? Can you put a lot of definitions in it. I THANK YOU!!! —Preceding unsigned comment added by 203.177.119.29 (talk • contribs) 06:20, 25 July 2006 (UTC)

you are talking a bout a diffrent line graph than what i want —Preceding unsigned comment added by 68.42.157.24 (talk • contribs) 19:20, 26 September 2007 (UTC)

If you could give some examples of the kind of line graphs you were looking for, we might be able to provide some links to information about them. —Ilmari Karonen (talk) 20:22, 26 September 2007 (UTC)

This whole article looks busy. Cut short the unnecessary things (just address what is needed). Also remember that we should shoot this for a non-mathematician - that's one of the goals of Wikipedia. Also this article is missing important refs.

You need not have to write evry thing here after addressing the main points. Put the resposnsiblities to references.

--Tangi-tamma (talk) 02:36, 6 April 2008 (UTC) Please do not yell at me.

Reference style

Since this is a math article, I suggest putting the references in the standard mathematical format, e.g., names in first-last order. Since I can't do that with harvtxt, I ask someone who can to fix them. Thank you. Zaslav (talk) 03:59, 16 April 2008 (UTC)

Re: "the standard mathematical format" for citations, please supply a reliable source for your assertion that such a thing exists. I don't believe that it does. And in any case, I think we should be aiming for a style that's more consistent across Wikipedia as a whole rather than splitting it up into incompatible fiefdoms. —David Eppstein (talk) 04:43, 16 April 2008 (UTC)

The source is reading 95+% of published math, and guidelines like (but not limited to) the AMS book on "Math Into Type" and the format guidelines provided by journals. This is hardly a secret. Maybe "standard" is ambiguous; change it to "usual". The rest of what you say is a matter of preference. I understood the Wikipedia guidelines to suggest following the format usual in each field as a perfectly viable alternative to following the "standard" Wikipedia format. If you disagree, please provide a source. Zaslav (talk) 18:41, 21 April 2008 (UTC)

Not that I think it's worth a lot of work, either way. I simply dislike the "last-first" name format and I claim it's legitimate not to use it in Wikipedia math articles. If you must change things, it's your lookout. Zaslav (talk) 18:46, 21 April 2008 (UTC)

Line graphs of convex polyhedra - wrong?

It says the cuboctahedron is the line graph of both the cube and the octahedron but this seems to contradict the Whitney isomorphism theorem. From some quick doodling I seem to find that the edge graph of the octahedron is a cuboctahedron plus extra edges connecting opposite vertices of the square faces. Gedkins (talk) 20:26, 5 August 2010 (UTC)

Yes, I think you're correct. Will fix. —David Eppstein (talk) 21:09, 5 August 2010 (UTC)

Reconstruction

"A graph G is the line graph of some other graph, if and only if it is possible to find a collection of cliques in G, partitioning the edges of G, such that each vertex of G belongs to at most two of the cliques. In order to do this, it may be necessary for some of the cliques to be single vertices." — This does not make any sense to me. I guess "at most" should read "exactly". This seems to be consistent with the rest of the article and would ensure that the reconstruction procedure (based on such a partition) results in an edge for each vertex of the line graph. The paper by Roussopoulos also uses the term "at most" to characterize line graphs, which is sufficient for characterization, but not the basis for reconstruction, I guess. --Nlskrg (talk) 00:16, 12 August 2010 (UTC)

"By the result of Whitney (1932),[3] if G is not a triangle, there can be only one partition of this type." — I think there may be more than one partition which, however, all lead to isomorphic graphs. --Nlskrg (talk) 00:16, 12 August 2010 (UTC)

The "theta-obrazom"? What?

The article said:

Other terms used for the line graph include edge graph, the theta-obrazom, the covering graph, the derivative, the edge-to-vertex dual, the interchange graph, the adjoint, the conjugate, the derived graph, and the representative graph.

And the bizarre term "theta-obrazom" caught my eye. Web searches did not turn up any other uses of this term, except those clearly derived from Wikipedia. (And one by some guy who used it to label a photograph of a fence that he thought resembled a histogram, which he apparently confused with "line graph".) It is conceivably a Russian term; "образ" means "style" or "manner". This might explain the failed web searches. But I suspect a prank.

When I checked the page history, I found that these terms were all added on January 2010 by a single-purpose account, Lostinaforest (talk · contribs). The terms are cited to:

• Hemminger, R. L.; Beineke, L. W. (1978), "Line graphs and line digraphs", in Beineke, L. W.; Wilson, R. J. (eds.), Selected Topics in Graph Theory, Academic Press Inc., pp. 271–305.
• Balakrishnan, V. K. (1997), Schaum's Outline of Graph Theory (1st ed.), McGraw-Hill, ISBN 0070054894.

I do not have Hemminger-Beineke handy, but I was able to check the reference at Balakrishnan; it is sound. However, it does not support "theta-obrazom". So I changed the citation format in the article, and cited each term separately. The four supported by Balakrishnan are now cited to Balakrishnan. If one presumes good faith, the other five can be cited to H-B, and that is what I have done. But this really ought to be checked. —Mark Dominus (talk) 15:53, 16 May 2011 (UTC)

This caught my eye, too. Beineke and Wilson's book is now on Google Books and the claim is genuine:

Technically, we should use the name &lqduo;edge graph”, but the name “line graph”, introduced in 1960 by Harary and Norman [23] (who used “lines” instead of “edges”), is now almost universally accepted. It has not always been so: Kotzig [40] called it the “ϑ-obrazom”, Fisher [16] the “covering graph” ...

Since ϑ-obrazom appears to be a very rare term, I've made it the last, rather than first alternative in the list of terms attributed to Beineke and Wilson. Dricherby (talk) 15:47, 18 November 2014 (UTC)

The word "obrazom" ("образом", pronounced OH-bruh-zuhm) is the singular instrumental form of Russian образ (OH-bruhz), which means "image", as in "f(x) is called the image of x". In a sentence "A is called B" in Russian, "B" would be in this exact instrumental declension. Now, the above quote from Beineke and Wilson's book cites Kotzig. According to Wiki, Anton Kotzig was a Slovak-born, Czecho-Slovak-educated, Slovak-Canadian mathematician. Nothing suggests Kotzig spoke Russian. I don't know if "obrazom" is a legit Slovak word, but it could be, judging from the following Czech phrase which I took from a Czech Wikipedia article [1] (Czech is much closer to Slovak than Russian):

Prvek $y=f(x)\in {\mathcal {B}}$ se nazývá obrazem prvku $x\,\!$

which translates into English roughly as

Element $y=f(x)\in {\mathcal {B}}$ is called the image of element $x\,\!$

No matter if "theta-obrazom" was transliterated from Slovak or from Russian, the nominative form "obraz" would be most appropriate for use in English. It is possible that Beineke, Hemminger and Wilson, being graph theory experts, knew nothing about declensions in Slavic languages at the time of writing in 1978. 72.139.202.163 (talk) 03:16, 28 July 2022 (UTC)

The algorithm

I think the line about the linear time algorithm could be expanded into a subsection describing the algorithm, and am working on such an expansion, but am temporarily stuck at an unclear point of the paper. Here is what I have so far:

Roussopoulos (1973) showed how to test whether a given graph is a line graph, and if so construct a graph G such that the input is isomorphic to L(G), in linear time. Roussopoulos's algorithm depends on two equivalent characterizations of line graphs described by Harary (1972): their edges can be covered by cliques such that each vertex belongs to exactly two cliques, and they are the claw-free graphs in which every two odd triangles with a shared edge belong to a common clique. Here, a triangle in a graph is said to be odd if there exists a vertex outside the triangle that is adjacent to an odd number of vertices inside the triangle, and even otherwise. An odd triangle in a line graph necessarily represents three edges that share a common endpoint, because the other way of forming a triangle (a triangle in G that translates into a triangle in L(G)) cannot be odd.

The first step of Roussopoulos' algorithm is to find a single clique in the clique cover of the supposed line graph input. To do so, the algorithm chooses an arbitrary edge e, and (by testing adjacency of its endpoints to the other vertices) finds all triangles involving e. If there are none, e is the desired clique. If there is only one triangle involving e, and the same property is true of the other two edges of the triangle, then this triangle is the desired clique. In the remaining case, the algorithm has found an edge (either e or one of the other edges of an initial triangle, which subsequently replaces e) that belongs to multiple triangles. [AT THIS POINT THE ALGORITHM COUNTS HOW MANY OF THE TRIANGLES AT e ARE ODD. HOW DOES IT DO IT?]

Will try to come back to this later. —David Eppstein (talk) 19:34, 8 November 2013 (UTC)

Ok, I now have a patch for this hole, but it raises a different question. We can mark every vertex of G as being odd if it is incident to exactly one endpoint of e, and even otherwise. Then a triangle formed by e and v is odd if the neighbors of v include an even vertex, or if they do not include all the odd vertices. Testing for this, for all triangles incident to e, takes time linear in the size of the graph. But now the question: since Roussopoulos doesn't mention this idea, is it original research? —David Eppstein (talk) 20:08, 8 November 2013 (UTC)

Resolution of the problem: it doesn't matter. The algorithm of Degiorgi & Simon (1995) (used for the static recognition problem despite being a dynamic algorithm) is much simpler, so that's the one to describe. —David Eppstein (talk) 22:14, 8 November 2013 (UTC)