The rank-width of the square grid |
| |
Authors: | Vít Jelínek |
| |
Institution: | Department of Applied Mathematics, Charles University, Prague, Czech Republic |
| |
Abstract: | Rank-width is a graph width parameter introduced by Oum and Seymour. It is known that a class of graphs has bounded rank-width if, and only if, it has bounded clique-width, and that the rank-width of G is less than or equal to its branch-width.The n×nsquare grid, denoted by Gn,n, is a graph on the vertex set {1,2,…,n}×{1,2,…,n}, where a vertex (x,y) is connected by an edge to a vertex (x′,y′) if and only if |x−x′|+|y−y′|=1.We prove that the rank-width of Gn,n is equal to n−1, thus solving an open problem of Oum. |
| |
Keywords: | Rank-width Grid graph Graph decomposition |
本文献已被 ScienceDirect 等数据库收录! |
|