Talk:Frequency partition of a graph

Can you create this subject on Wikipedia ? It is good to have a subject "Frequency Partition" rather than writing it on a different page. It is related to the subject Degree sequence in Graph Theory. Let me know what is the best way to write about "Frequency Partition" in Graph Theory. --Tangi-tamma (talk) 16:52, 16 March 2008 (UTC)[reply]

Administrators should have some patience and wait for some time if they do not follow. --Tangi-tamma (talk) 17:34, 16 March 2008 (UTC)[reply]

I have tagged for context again as the article makes no attempt to define "frequency partition". Please try to write a sentence which starts with "In graph theory, the frequency partition of a graph is..." and put that at the start of the article. This may be obvious to you but it will provide introduction and context for readers who are not yet familiar with the subject and are reading the article to find out about it. You might also like to reuse one or more the diagrams on Degree (graph theory) to illustrate the subject. --DanielRigal (talk) 20:26, 16 March 2008 (UTC)[reply]

Errors ? Keep this

The article contains some apparent errors:

1. "Chinn proved that given any partition p= f1+f2+...+fk of an integer p > 1, other than p = 1+1+1+...+1, there is at least one (connected) graph having this partition as its frequency partition".This result seems to be incorrect. Counterexamples:

There is no graph with frequency partition (1,2) i.e. one vertex with degree 1 and two vertices with degree 2.
There is no connected graph with frequency partition (4,1) i.e. four vertices with degree 1 and one vertex with degree 2.

2. "There can be several degree sequences compatible with a given frequency partition". Unless I have misunderstood how frequency partitions work, this cannot be correct. Surely the degree sequence can be simply read off from the frequency partition - a graph with frequency partition (1,4,1) must have degree sequence (1, 2, 2, 2, 2, 3). How can there be any ambiguity in translating from frequency partition back to degree sequence ?

3. "It is obvious that a graph G and its complementary graph have the same frequency partition". This also appears to be incorrect. The complement of a connected graph may not even be connected. Where it is connected, its frequency partition will run in the opposite order to the original graph. Take, for example, a graph (0,3,2) with three vertices with degree 2 and two vertices with degree 3. Its complement has two vertices with degree 1 and three vertices with degree 2, and so has frequency parition (2,3).

It occurs to me that some of these apparent errors could be explained if the "frequency partition" is, in fact, unordered (as the term "partition" would seem to suggest). Thus a frequency partition of (2,3) would mean the graph has two vertices with some degree (not necessarily 1) and three vertices with some other degree (not necessarily 2). This is not clear from the single example in the article. What the article needs is a proper definition of its subject. Gandalf61 (talk) 13:39, 18 March 2008 (UTC)[reply]

I will get back to you with explanations - Hopefully during weekends. It might be how I have wriiten it or how you took it. Thanks.

--Tangi-tamma (talk) 22:06, 18 March 2008 (UTC)[reply]

I have added another example. Hope it helps. Let me know if you have further questions. For FP (1,2), consider the claw graph with 3 vertices, and degree sequence (2, 2, 1).

To understand the degree sequences, you have to look somewhere on Wikipedia. I do not think I need to write here what is graphic sequence.

--Tangi-tamma (talk) 01:20, 19 March 2008 (UTC)[reply]

You new example helps a little - it seems to indicate that the frequency partition of a graph is an unordered list. However, the article still does not give a definition of a frequency partition. The article needs to have a sentence in its lead paragraph that begins with "The frequency partition of a graph is ..." and goes on to define a frequency partition. At present the article just says "the frequency partition of a graph is related to its degree sequence", which is not sufficient. One of the references that you have listed at the end of the article must surely give a suitable definition.

There is no graph with degree sequence (2,2,1) because the sum of the degrees in a degree sequence must be even (see Degree Sequence at Mathworld), whereas the sum of degrees in (2,2,1) is 5, which is odd. The claw graph with 3 vertices actually has degree sequence (2,1,1). So - is the frequency partition of this graph (2,1) or is it (1,2) - or are they actually the same ?

Here is another simple question. The complete graph K₄ has four vertices each of which has degree 3. Is its frequency partition (0,0,4) or is it just (4) or is it something else ? Gandalf61 (talk) 09:53, 19 March 2008 (UTC)[reply]

Okay, no answer after several days, so I am going to assume that a frequency partition is an unordered list, and edit the article myself to give a definition. References also need converting to in-line reference format, and the whole thing can be trimmed down a bit. Gandalf61 (talk) 16:15, 24 March 2008 (UTC)[reply]