论文标题
等级连通性和图形的枢轴少量
Rank connectivity and pivot-minors of graphs
论文作者
论文摘要
图$ g $中的$ x $的切割量是二进制字段上邻接矩阵的$ x \ times（v（g）-x）$ subbatrix的排名。拆分是将顶点设置为两个集合$（x，y）$的分区，因此$ x $的切割额为少于$ 2 $，$ x $和$ y $都至少有两个顶点。如果将图是素数（相对于拆分分解），则该图是连接的，没有分裂。图$ g $是$ k^{+\ ell} $ - 级别连接，如果对于每种$ x $的顶点，切割量小于$ k $，$ \ lvert x \ rvert $或$ \ lvert v（g）-x \ rvert $均小于$ k+\ el ell eth $。我们证明，每个Prime $ 3^{+2} $ - 与级别连接的Graph $ g $，至少$ 10 $ Vertices具有Prime $ 3^{+3} $ - 与等级连接的pivot-minor $ h $，因此$ \ lvert V（h）\ rvert v（h）\ rvert = \ lvert v（g）\ lvert v（g）\ rvert-rvert -1 $。作为推论，我们表明，最多$ k $的每一个排除级别差的枢轴最多都有$（3.5 \ cdot 6^{k} -1）/5 $ the $ k \ ge 2 $。我们还表明，最多$ 2 $的排名宽度级别的枢轴最多最多为$ 16 $。
The cut-rank of a set $X$ in a graph $G$ is the rank of the $X\times (V(G)-X)$ submatrix of the adjacency matrix over the binary field. A split is a partition of the vertex set into two sets $(X,Y)$ such that the cut-rank of $X$ is less than $2$ and both $X$ and $Y$ have at least two vertices. A graph is prime (with respect to the split decomposition) if it is connected and has no splits. A graph $G$ is $k^{+\ell}$-rank-connected if for every set $X$ of vertices with the cut-rank less than $k$, $\lvert X\rvert$ or $\lvert V(G)-X\rvert $ is less than $k+\ell$. We prove that every prime $3^{+2}$-rank-connected graph $G$ with at least $10$ vertices has a prime $3^{+3}$-rank-connected pivot-minor $H$ such that $\lvert V(H)\rvert =\lvert V(G)\rvert -1$. As a corollary, we show that every excluded pivot-minor for the class of graphs of rank-width at most $k$ has at most $(3.5 \cdot 6^{k}-1)/5$ vertices for $k\ge 2$. We also show that the excluded pivot-minors for the class of graphs of rank-width at most $2$ have at most $16$ vertices.
