Jump to content

Talk:Frequency partition of a graph

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Michael Hardy (talk | contribs) at 17:44, 18 March 2008 (moved Talk:Frequency Partition to Talk:Frequency partition). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 ?

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]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Frequency_partition_of_a_graph&oldid=199129909"