This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
I'm not sure it's needed to explain every technical thing in the Wikipedia in a language that anyone would understand. For instance, the explanation for this still-simple article seams quite absurd ( Mariano 16:46, 25 August 2005 (UTC)):
1. Can be constructed from (1) isolated vertices by (2) complement and (3) disjoint union. This means that:
And, tat any Cograph can be constructed following this 3 rules.
2. Can be (1) decomposed by (2) isolated vertex elimination and complement. G ∪ {x} (G union an element x) is also a Cograph This means that we can play "She loves me, she loves me not" with the graph, taking vertices that are not connected to any other vertex, or complement the graph, and we will end up with an empty graph.
3. It contains no induced [Glossary_of_graph_theory#Path|path]] of length at least 4. A P4 of a graph is a path of 4 distinct vertices a, b, c and d, with a connected to b, b connected to c, and c connected to d, such that to go from a to b I have no shortcut. Therefore, if our graph G has a P4, then is not a Cograph, and if it doesn't have it, it is a Cograph.
4. The maximum distance between two vertices in the same connected component is at most 2. If there is a path from a to b, then the shortest path between them includes one more vertex, or none at all.
5. Has at least one pair of false or true twins (that have the same opened or closed neighbourhood). This means that if G is a Cograph, then there must exist vertices a and b such that all the neighbours of a are also neighbours of b. Bear in mind that it doesn't matter if a and b are neighbours.
I tried to simplify the entry. I stressed the constructive definition, which is not so difficult to handle and gave some of the possible other ones as characterizations (formally, we may not have more than one definition). I removed the characterization by twins which has mainly a technical interest, but I kept:
I also have added some references.
pom 14:50, 14 November 2005 (UTC)
As noticed by D. Eppstein, Cographs are not a parametrized family hence should not belong to Category:Graph. pom 23:56, 5 October 2006 (UTC)
First, my substantive comment. I augmented the first characterization by explicitly including the notation P4. Since the article's introduction points out that the cographs are also known as the P4-free graphs, I figured it would add to the article's clarity if this P4 thing showed up somewhere below to tie things together.
Now a confession. I did it once and accidentally saved the page without having cretaed a comment to document the change in the history. So I immediately undid the change and re-implemented it, this time including the comment. That explains the 3 mods in such quick succession.— PaulTanenbaum ( talk) 20:28, 9 July 2008 (UTC)
Where can I find a proof for that. I searched for that in all the given References. —Preceding unsigned comment added by 141.20.6.79 ( talk) 18:38, 9 March 2011 (UTC)
The concept of (disjoint) union is generally defined only for sets, which graphs are not because they are pairs of sets.
If an abuse of notation is being adopted, it should be clarified somewhere. — Preceding unsigned comment added by 213.46.252.136 ( talk) 10:41, 12 January 2015 (UTC)
The comment(s) below were originally left at Talk:Cograph/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
Too high a ratio of lists to text. — David Eppstein 03:23, 14 May 2007 (UTC) |
Last edited at 03:23, 14 May 2007 (UTC). Substituted at 01:53, 5 May 2016 (UTC)
This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
I'm not sure it's needed to explain every technical thing in the Wikipedia in a language that anyone would understand. For instance, the explanation for this still-simple article seams quite absurd ( Mariano 16:46, 25 August 2005 (UTC)):
1. Can be constructed from (1) isolated vertices by (2) complement and (3) disjoint union. This means that:
And, tat any Cograph can be constructed following this 3 rules.
2. Can be (1) decomposed by (2) isolated vertex elimination and complement. G ∪ {x} (G union an element x) is also a Cograph This means that we can play "She loves me, she loves me not" with the graph, taking vertices that are not connected to any other vertex, or complement the graph, and we will end up with an empty graph.
3. It contains no induced [Glossary_of_graph_theory#Path|path]] of length at least 4. A P4 of a graph is a path of 4 distinct vertices a, b, c and d, with a connected to b, b connected to c, and c connected to d, such that to go from a to b I have no shortcut. Therefore, if our graph G has a P4, then is not a Cograph, and if it doesn't have it, it is a Cograph.
4. The maximum distance between two vertices in the same connected component is at most 2. If there is a path from a to b, then the shortest path between them includes one more vertex, or none at all.
5. Has at least one pair of false or true twins (that have the same opened or closed neighbourhood). This means that if G is a Cograph, then there must exist vertices a and b such that all the neighbours of a are also neighbours of b. Bear in mind that it doesn't matter if a and b are neighbours.
I tried to simplify the entry. I stressed the constructive definition, which is not so difficult to handle and gave some of the possible other ones as characterizations (formally, we may not have more than one definition). I removed the characterization by twins which has mainly a technical interest, but I kept:
I also have added some references.
pom 14:50, 14 November 2005 (UTC)
As noticed by D. Eppstein, Cographs are not a parametrized family hence should not belong to Category:Graph. pom 23:56, 5 October 2006 (UTC)
First, my substantive comment. I augmented the first characterization by explicitly including the notation P4. Since the article's introduction points out that the cographs are also known as the P4-free graphs, I figured it would add to the article's clarity if this P4 thing showed up somewhere below to tie things together.
Now a confession. I did it once and accidentally saved the page without having cretaed a comment to document the change in the history. So I immediately undid the change and re-implemented it, this time including the comment. That explains the 3 mods in such quick succession.— PaulTanenbaum ( talk) 20:28, 9 July 2008 (UTC)
Where can I find a proof for that. I searched for that in all the given References. —Preceding unsigned comment added by 141.20.6.79 ( talk) 18:38, 9 March 2011 (UTC)
The concept of (disjoint) union is generally defined only for sets, which graphs are not because they are pairs of sets.
If an abuse of notation is being adopted, it should be clarified somewhere. — Preceding unsigned comment added by 213.46.252.136 ( talk) 10:41, 12 January 2015 (UTC)
The comment(s) below were originally left at Talk:Cograph/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
Too high a ratio of lists to text. — David Eppstein 03:23, 14 May 2007 (UTC) |
Last edited at 03:23, 14 May 2007 (UTC). Substituted at 01:53, 5 May 2016 (UTC)