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:
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“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)