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)
“Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
—Nadine Gordimer (b. 1923)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)