Talk:Cycle graph

Note on origin of this page

Was brought from talk: cyclic graph. This page's talk page (this page) used to redirect to talk: cycle graph (old). Gah, what a mess! Hopefully this is all sorted out now:Debivort 03:39, 8 January 2006 (UTC)

---

---

I removed the previous content from the page and did a rewrite. I do not really understand what the author is talking about here

A circle graph is a circle with n equidistant points. (In graph theory, the proper term would be "vertex.") It represents the remainder of x divided by n (called the modulus of integer division). It is useful in number theory for finding interesting properties of series. It is also useful for teaching children about repeating end digits in multiplication: a circle graph with 10 vertices, with the multiples of three graphed in sequence, results in [0,3,6,9,2,5,8,1,4,7,0], with the sequence infinitely repeating.

MathMartin 14:10, 10 Jan 2005 (UTC)

this page

This page is very confused between simple and non-simple cycles. The useful material should be moved to path (graph theory) and then this page should become a redirect to there. I vote for dropping "circle graph" as it is hardly ever used. --Zero 10:12, 11 August 2005 (UTC)

I repeat this opinion. It is a mess. --Zero 03:11, 4 September 2005 (UTC)

I agree. Part of the problem is caused by non-standard terminology used in textbooks of graph theory. Maybe we can keep (simple) cycle (graph) here and delete or move elsewhere the directed and non-simple version. Tomo 06:28, 4 September 2005 (UTC)

How about now? --Zero 08:00, 4 September 2005 (UTC)

Layman's Terms

we should probably explain mathy stuff in layman's terms (in a separate section called "layman's terms" or "simple terms" or something, This would make Wikipedia exponentially more useful to common student users. ??Is this an order accurate description?? If outputs oscillate between state variable values, and the representative sinusoidal curves have a finite number of possible amplitudes, this is a cycle graph. These amplitude possibilities are "cycled" through directionally. ?? — Preceding unsigned comment added by Jgreeter (talk • contribs) 11:32, 24 April 2011 (UTC)

You seem to be writing about some entirely different subject than what this article is about. Here we are talking about graphs that are collections of vertices and edges, not graphs that are drawings of functions. —David Eppstein (talk) 16:03, 24 April 2011 (UTC)

Cyclic graph

I moved it to "cyclic graph", since that term covers only simple cycle graphs, which is what is being talked about here. Gene Ward Smith 21:54, 6 December 2005 (UTC)

These changes

Gene, your changes are completely wrong. A "cycle graph" or just "cycle" in graph theory is what was described here before. In group theory, a "cycle graph" is a graph showing the structure of cycles in a group. These are the two meanings of "cycle graph". I've never seen your new definition in decades of experience in this field. Where did you get it? --Zero 12:46, 7 December 2005 (UTC)

I don't think this issue is satisfactorily resolved. In fact, while I think the term cyclic graph is most appropriately applied to n-gons, rather than cycle graph which is the graph of cycles generated by taking gⁿ where g element of some group G. In fact, Zero, when you changed the external link, you changed it from a link to a page on n-gons to this latter algebraic graph. While Gene's definition did seem a bit awkward, it was properly named. I think we need the following: cycle graph (group) renamed to cycle graph. The current cycle graph renamed to cyclic graph. Both pages will then need disambiguation links to each other, and to the other meanings currently disambiguated at cyclic graph. - Gene's changes weren't completely wrong, and in fact are supported by the very external links you implemented. -- Debivort 05:18, 7 January 2006 (UTC)

I strongly disagree. Graph theorists call these "cycles" and sometimes "polygons" or "n-gons" if they want to specify the length. I have never seen them called "cyclic graphs" except on that one page at Mathworld, and the reference there does not agree with that definition. (Enumeration of polygons is trivial; Balaban is enumerating some class of graphs that contain cycles, not just graphs that are cycles. I'll check this on Monday.) I asked two professional graph theorists, one the editor of a graph theory journal, and they also could not remember hearing cycles called "cyclic graphs". Then I went through that first few pages of results of searching for "cyclic graph" at MathSciNet (index of academic mathematical literature) and I didn't see any such uses. The most common meaning is circulant graph. So, I repeat my request: where, apart from Mathworld, did you get this idea? --Zero 11:58, 7 January 2006 (UTC)

Alrightee: if one googles ["cyclic graph" site:arxiv.org][1], you get 25 hits.

The following results use the "cyclic graph" to indicate a n-gon, sensu me and Gene: #1, #2, though in a single buried usage, #4, #7, #8 = #9, #11, #14, #17, #19, #21, #21(?), #23 by Donald Knuth!,

Thanks for doing that work. It is appreciated. Two corrections: #2 means "circulant graph", which is a very common usage in graph theory; #14 probably means "graph with at least one cycle". That leaves Knuth's paper as the only one in graph theory (rather than in an application area) that uses cyclic graph to mean a cycle. Meanwhile someone asked on a graph theory mailing list and one person found a textbook using it that way after looking in many. So the revised conclusion is that this usage is rare (but exists) in graph theory but fairly common in other areas of mathematics or application areas. --Zero 02:05, 8 January 2006 (UTC)

The following use the term to mean "a graph containing cycles" (often computer science papers): #3, #13, #20,

I'm told by a chemist that they use it in this meaning sometimes, to distinguish molecules with rings of bonds from those without. --Zero 02:05, 8 January 2006 (UTC)

The following don't use the term as a term, i.e. they have phrases like "blah blah blah cyclic. Graphs are tasty...": #5 = #6,

The following I can't tell, or use what seems to be a fairly common quantum mechanics usage: #10, #12, #15, #16, #18, #24 a ref, #25

----

Complementary google search: ["cycle graph" site:arxiv.org] gives 19 hits:

The following use "cycle graph" sensu you (i.e. "cyclic graph" sensu us): #1=#18, #4, #8, #9, #10, #11, #13, #14, #15, #16, #17,

The following use "cycle graph" as a graph in which nodes represent cycles of another graph: #2, #3, #5, #6=#7, #12,

The following don't use the term as a term, i.e. they have phrases like "blah blah blah cyclic. Graphs are tasty...": #19,

---- So, 11/17 real google/arxiv votes for "cycle graph"=n-gon, and 12/23 votes for "cyclic graph"=n-gon, by this sample both terms have the same majority meaning and are used with roughly the same frequency. So, apart from MathWorld, this is where I got the idea. I'd propose the following: 1) we get rid of the silly disambig at cyclic graph 2) cycle graph redirects to cyclic graph, or vice versa and that page has the n-gon content. 3) we make a cyclic graph (disambiguation) = cycle graph (disambiguation), and 4) we rename cycle graph (group) to cycle graph (algebra) as a more appropriate general name. Debivort 22:42, 7 January 2006 (UTC)

Almost the same suggestion.: Two real pages "cycle graph" and "cycle graph (algebra)", and one redirect from "cyclic graph" to "cycle graph". Of course the "cycle graph" page will explain that both "cycle" and "cyclic" are in use. --Zero 02:05, 8 January 2006 (UTC)

I agree. glad we could come to a consensus on that. I'll set about making the changes you have outlined above. Let me know if the end version isn't satisfactory. Debivort 03:23, 8 January 2006 (UTC)

Those changes

Some comments on my recent changes: It's strange that MathWorld uses "cyclic graph" to refer to a graph which is a cycle, as opposed to a graph which has a cycle; surely "cyclic" and "acyclic" are opposites!

It's not obvious to me that cycle graphs are symmetric, so I added a {{fact}} tag. I think the editor may have been thinking of circulant graphs, which are totally different animals.

There is a commented-out image at the top of the section "Directed cycle graph" whose caption implies that an "hourglass-shaped" graph would be a cycle graph. That's not the way I've ever heard the term used. (A cycle may be non-simple, but a cycle graph is always simple.)

• If hourglass-shaped graphs are cycles, then the property "2-regular" needs to be removed from the list of properties of cycle graphs. (That removal seems ridiculous to me, which is why I don't think anyone's likely to defend it.)
• If hourglass-shaped graphs are cycles, then consider reverting my removal of the claim that There is a directed cycle through any two vertices in a strongly connected component. That's obviously not true if the directed cycle has to be a simple cycle. However, even if we let it be true, I don't think it's terribly relevant to the topic of cycle graphs. --Quuxplusone 00:59, 22 December 2006 (UTC)

Whoops, never mind some of those comments. MathWorld does use "cycle graph"; the page "Cyclic graph" is empty, so I don't know why we link to it. And we need to distinguish between a cycle graph, for example C₅, which is 2-regular; and the cycle graph of a group, for example C₂×C₂, which is not. And those "hourglass-shaped" graphs are indeed not cycle graphs; the word for them is "Eulerian". --Quuxplusone 01:05, 22 December 2006 (UTC)

this nnot a circle graph —Preceding unsigned comment added by 207.166.228.91 (talk) 14:57, 12 October 2007 (UTC)

Do you mean circular arc graph, maybe? That would be a different article, if it existed. —David Eppstein 15:12, 12 October 2007 (UTC)

Different meanings

Cycle graph and cyclic graph are not the same. "Preorder" entry wrongly links to "cycle graph", it should link to "cyclic graph", where "cyclic graph" is used for something other than cycle graphs. "Cyclic graph" should not be redirected to "cycle graph" indiscriminately. I'm introducing a stump for cyclic graph and remove the redirect. Cf. e.g. MathWorld, which I think gets it right. Flosfa (talk) 18:18, 20 August 2015 (UTC)

I'm afraid people are using these terms with many different meanings. In http://mathworld.wolfram.com/CyclicGraph.html, "cyclic" is used as synonymous with "not acyclic"; there is a certain logic in this usage, but that does not make it "the correct one". Indeed, mathworld warns the user of the fact that there are several other usages.

In Small Ramsey Numbers (Electronic Journal of Combinatorics, dynamic survey, updated 2014), Stanisław Radziszowski uses "cyclic graph" in the sense given to circulant graph in our article. Now, the EJC DS1 is not a negligible item in this context; but I'd like to know how widespread Radziszowski's usage is. JoergenB (talk) 12:01, 8 May 2016 (UTC)

This article is about one specific choice among these meanings, not about other meanings for the same name. For that, see the disambiguation link at the top of the article. —David Eppstein (talk) 17:53, 8 May 2016 (UTC)