This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
The pathwidth of a tree is almost the same thing as its Strahler number, right? Can this observation be sourced, adequately enough to include it in the article? — David Eppstein ( talk) 17:31, 1 April 2009 (UTC)
In section 2.4 of their book, Bondy and Murty provide a different definition for path decomposition. ( This link might show you the page in question.) It's actually a *very* loose (and less interesting) definition of decomposition; they include any family of edge-disjoint subgraphs such that every edge belongs to one of the subgraphs.
They then give "Veblen's theorem" that says (just like necessary and sufficient conditions for the existence of an Eulerian circuit), a graph may have a cycle decomposition iff every vertex has even degree. (The current article has little to do with this definition of "cycle decomposition".) Justin W Smith talk/ stalk 05:04, 8 May 2010 (UTC)
I few more things I want to note here:
Justin W Smith talk/ stalk 05:17, 9 May 2010 (UTC)
The introduction to this article is absolutely absymal. After reading it I was so frustrated with the poor quality of the introduction that I seriously considered rewriting this myself, which I don't ever do. Pathwidth and path decomposition are two distinctly different concepts and should be treated as such. You should remove all reference to pathwidth in the introduction and form its own section or its own page. At the very least, give it a separate sentance.
Better would be something more like this:
In graph theory a path-decomposition is a sequence of subsets of vertices of a graph such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets.[2] Path-decompositions are closely analogous to tree decompositions. They play a key role in the theory of graph minors.
66.87.4.250 ( talk) 06:35, 26 December 2012 (UTC)
This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
The pathwidth of a tree is almost the same thing as its Strahler number, right? Can this observation be sourced, adequately enough to include it in the article? — David Eppstein ( talk) 17:31, 1 April 2009 (UTC)
In section 2.4 of their book, Bondy and Murty provide a different definition for path decomposition. ( This link might show you the page in question.) It's actually a *very* loose (and less interesting) definition of decomposition; they include any family of edge-disjoint subgraphs such that every edge belongs to one of the subgraphs.
They then give "Veblen's theorem" that says (just like necessary and sufficient conditions for the existence of an Eulerian circuit), a graph may have a cycle decomposition iff every vertex has even degree. (The current article has little to do with this definition of "cycle decomposition".) Justin W Smith talk/ stalk 05:04, 8 May 2010 (UTC)
I few more things I want to note here:
Justin W Smith talk/ stalk 05:17, 9 May 2010 (UTC)
The introduction to this article is absolutely absymal. After reading it I was so frustrated with the poor quality of the introduction that I seriously considered rewriting this myself, which I don't ever do. Pathwidth and path decomposition are two distinctly different concepts and should be treated as such. You should remove all reference to pathwidth in the introduction and form its own section or its own page. At the very least, give it a separate sentance.
Better would be something more like this:
In graph theory a path-decomposition is a sequence of subsets of vertices of a graph such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets.[2] Path-decompositions are closely analogous to tree decompositions. They play a key role in the theory of graph minors.
66.87.4.250 ( talk) 06:35, 26 December 2012 (UTC)