We prove that every graph of rank-width $k$ is a pivot-minor
of a graph of tree-width at most $2k$ and every graph of linear rank-width $k$ is
a pivot-minor of a graph of path-width at most $k+1$.
We also prove that graphs of rank-width
at most $1$ are exactly vertex-minors of trees, and graphs of linear rank-width
at most $1$ are precisely vertex-minors of paths. In addition, we show that
bipartite graphs of rank-width at most $1$ are exactly pivot-minors of trees
and bipartite graphs of linear rank-width at most $1$ are precisely
pivot-minors of paths.
Also, we calculate the linear rank-width of complete binary trees. And we show that if a tree has linear rank-width at least $k$, then it has the complete binary tree of height $k$ as a vertex-minor. Finally, we describe an interesting question that a class of graphs with unbounded linear rank-width contains all trees as vertex-minors or pivot-minors. We prove that this question for pivot-minor is false and we suggest another version of the question.

- Advisors
- Oum, Sang-Il
*researcher*; 엄상일

- Description
- 한국과학기술원 : 수리과학과,

- Publisher
- 한국과학기술원

- Issue Date
- 2012

- Identifier
- 509386/325007 / 020104251

- Language
- eng

- Description
학위논문(석사) - 한국과학기술원 : 수리과학과, 2012.8, [ iv, 29 p. ]

- Keywords
rank-width; tree-width; vertex-minor; rank-width; tree-width; vertex-minor; pivot-minor; pivot-minor

- Appears in Collection
- MA-Theses_Master(석사논문)

- Files in This Item
- There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.