Definition
In the first of their famous series of papers on graph minors, Neil Robertson and Paul Seymour (1983) define a path-decomposition of a graph G to be a sequence of subsets Xi of vertices of G, with two properties:
- For each edge of G, there exists an i such that both endpoints of the edge belong to subset Xi, and
- For every three indices i ≤ j ≤ k, Xi ∩ Xk ⊆ Xj.
The second of these two properties is equivalent to requiring that the subsets containing any particular vertex form a contiguous subsequence of the whole sequence. In the language of the later papers in Robertson and Seymour's graph minor series, a path-decomposition is a tree decomposition (X,T) in which the underlying tree T of the decomposition is a path graph.
The width of a path-decomposition is defined in the same way as for tree-decompositions, as maxi |Xi| − 1, and the pathwidth of G is the minimum width of any path-decomposition of G. The subtraction of one from the size of Xi in this definition makes little difference in most applications of pathwidth, but is used to make the pathwidth of a path graph be equal to one.
Read more about this topic: Path Decomposition
Famous quotes containing the word definition:
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)