Talk:Degree (graph theory)

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Stub Class	Low Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Geometry guy 21:54, 1 June 2007 (UTC)

Contents 1 Image:Depth-first-tree 2 Degree sum formula 3 [edit] Graph (degree) 4 I recommend changing the title "Degree (Graph theory)" to one of the followings 5 Undirected graph 6 Removed section 6.1 0.25

[edit] Image:Depth-first-tree

Someone needs to fix the graph with the caption "An undirected graph with leaf nodes 4, 5, 6, 7, 10, 11, and 12". Node 10 is depicted as "18" in the graph. Figs 19:57, 14 March 2007 (UTC)

No its not. The zero just got a dot in it that makes i look like 18 if you dont look carefully. :) —Preceding unsigned comment added by 129.16.25.17 (talk) 11:23, 13 March 2008 (UTC)

[edit] Degree sum formula

I'm boldly redirecting Degree sum formula (present version) to this article, since it has been a stub for two years now and its content is already here. Melchoir (talk) 05:03, 22 March 2008 (UTC)

[edit] [edit] Graph (degree)

I'm still working on it. It will take a few days to complete. Thanks.

Is hangon code ok? --Tangi-tamma (talk) 11:12, 19 April 2008 (UTC)

No, the hangon tag is inappropriate - if you read its text, you will see that it refers specifically to a speedy deletion proposal. I suggest you remove it. {3,3,3,1} is a bad example of a sequence that is not a degree sequence, because there is a graph with this degree sequence - it is just not a simple graph. As the example comes immediately after presenting the degree sum formula, a sequence like {3,3,1} that clearly breaks this rule is a much better example. Gandalf61 (talk) 11:28, 19 April 2008 (UTC) We are talking here simple graphs (no loops, no multiple edges - read it carefully. It comes under the heading undirecteed (no loops, no multiple edges.). There is no graph with (3, 3, 3, 1), yes there is one with this if you consider graphs with loops or multiple edges; I do not find charm with degree sequences of graphs with loops or multiple edges (it is trivial). I'm writing for simple graphs.

If you do not like it, I will stop writing this article.

Let me know what code you are suggesting.

--Tangi-tamma (talk) 12:52, 19 April 2008 (UTC)

Retrieved from "http://en.wikipedia.org/wiki/User_talk:Gandalf61"

--Tangi-tamma (talk) 14:11, 19 April 2008 (UTC) Let me know what code you are suggesting.

--Tangi-tamma (talk) 12:52, 19 April 2008 (UTC)

The graph theory literature is, unfortunately, not consistent in its definitions. Sometimes the term "graph" implies a simple graph, sometimes it is used to mean a graph that may have multiple edges, or loops, or both.

When illustrating a statement such as "not every sequence is the degree sequence of a graph" it is best to use an example that is as simple as possible. It is not obvious that there is no (simple) graph with degree sequence {3,3,3,1}. It is more obvious, once the degree sum formula is known, that there can be no graph with degree sequence {3,3,1}. My example is simpler and therefore better.

Yes, I would prefer you to stop editing the Degree (graph theory) article. Your edits are often confusing, and sometimes wrong. Gandalf61 (talk) 15:09, 19 April 2008 (UTC)

You wrote ":The graph theory literature is, unfortunately, not consistent in its definitions". I think you need to work on fixing the connfusion for the article that somone wrote here. I'm not understanding what you are trying to influence? I want someone to intrevene here. You are pointing here at everybody including me when you are failing to understand the subject. The degree sequence that I'm talking here is for graphs without loops and multiple edges. Let me know what was confusing for you on this article. I'm setting the article for cleanup. --Tangi-tamma (talk) 17:02, 19 April 2008 (UTC)

Fine, I'll intervene; I agree with Gandalf61. This is not to say that simple graphs should not be discussed at all, but they come later in the logical progression. Melchoir (talk) 19:46, 19 April 2008 (UTC)

A baby example was given. Updated with a solid example. Also updated the definition of simple graphs to avoid confusion. Thanks God someone tried to understand the material. --Tangi-tamma (talk) 21:45, 19 April 2008 (UTC)

I'm not really comfortable with that characterization of the situation... anyway, there's some more cleanup that I'll do. Melchoir (talk) 02:19, 22 April 2008 (UTC)

[edit] I recommend changing the title "Degree (Graph theory)" to one of the followings

1. Degree sequence.

2. Degree sequence of graphs and hypergraphs.

Degree sequence is itself pretty big. The Graph (mathematics) covers the basic definitions of graphs. --Tangi-tamma (talk) 13:41, 20 April 2008 (UTC)

Oppose. "Degree sequence" is already re-directed here. "Degree sequence of graphs and hypergraphs" is not likely to be a search term. Leave title as is. Gandalf61 (talk) 16:48, 20 April 2008 (UTC)

How about changing it to "Degree sequence" rather than calling it as "Degree (Graph Theory)"? That does not sound good. --Tangi-tamma (talk) 18:54, 20 April 2008 (UTC)

This article is not only about degree sequences. Renaming it to "Degree sequence" would suggest that all degree-related data in a graph can be derived from its degree sequence, which is not the case. If "Degree (graph theory)" is really that unpalatable, then an equivalent title without parentheses would be "Degree of a vertex". Melchoir (talk) 02:16, 22 April 2008 (UTC)

Degree is a very important concept in graph theory, and lots of articles link here. We need to keep this article. Degree sequences may fit in as a subsection (my preference), or perhaps as an article on their own. Radagast3 (talk) 06:23, 1 May 2008 (UTC)

[edit] Undirected graph

The para needs editing using the math symbols. --Tangi-tamma (talk) 20:29, 20 April 2008 (UTC)

[edit] Removed section

I removed the following new section of text from the article:

Let P be any property that goes with a graph. Crispin St. J. A. Nash-Williams called a graphic degree sequence a Potentially P if the graphic degree sequence has at least one realization with property P. He called a Forcibly P if every realization of the graphic degree sequence has that property P. These concepts set forth a series of open research problems in degree sequence.

The sequence (13, 12, 11, 10, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2) on 14 vertices is an example of a forcibly Hamiltonian graphic sequence. The sequence (2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2) is an example of a potentially Hamiltonian graphic sequence. The problem of characterization of forcibly Hamiltonian graphic degree sequences is a classical open problem.

Removed because: 1) It is badly written and barely coherent. 2) As it appears to be talking about an open problem concerning Hamiltonian graphs, it does not belong in this article anyway. Gandalf61 (talk) 08:21, 21 April 2008 (UTC)

I would say agian that this is someone's ability to understand. --Tangi-tamma (talk) 13:15, 21 April 2008 (UTC)

I have dropped the idea of writing about degree sequences in detail. Let us make a deal here.

The deal is who cares about Forcibly.......from Williams.

We will just add the line : The sequence (13, 12, 11, 10, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2) of 14 vertices is an example of a Hamiltonian graphic degree sequence. (If you and Consensus do not feel comfortable, you may delete it.). --Tangi-tamma (talk) 22:55, 21 April 2008 (UTC)

I don't see the point of that sentence. The sequence (2, 2, 2) is also the degree sequence of a Hamiltonian graph, but who cares? Melchoir (talk) 02:30, 22 April 2008 (UTC)

[edit] 0.25

It is better to remove the portion when someone plays with rm. Since I do not have the citation, I cannot give it at this time. I will place the section here for future use if someone is able to get the reference.

The verification is as simple as understnding the simple graphs. Sosmeone could verify it easily. I cannot post the code that gets that number stated there.

Here is the piece.

Let p be any positive even integer. Let P(p) denote the set of all partitions of p. A partition in P(p) is graphical if it is the degree sequence of some simple graph. For example, (5,4, 4, 2, 2, 1) is not graphical. Let G(p) denote the set of all graphical partitions of p. The computation of |G(p)| can be done in O(p⁴). For p = 50, |G(p)| = 76104 and |P(p)| = 204,226. Thus the ratio |G(p)| to |P(p)| tends to 0.25 as p tends infinity.^{[citation needed]}

Also notice that some said about Erdos paper, but he/she forgot to cite. How about this? --Tangi-tamma (talk) 13:15, 21 April 2008 (UTC)

If you mean my edits, I could cite them to some random book found on Google, as could any reader very quickly. As long as the material isn't being challenged, I'd prefer if someone took the time to find a really good reference, preferably a review article. Melchoir (talk) 02:33, 22 April 2008 (UTC)