This is the talk page for discussing improvements to the Line graph article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This level-5 vital article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
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)
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.
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)
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)
"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 article said:
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:
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)
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” ...
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 se nazývá obrazem prvku
which translates into English roughly as
Element is called the image of element
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)
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:
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)