Rooted topological minors on four vertices
Rooted topological minors on four vertices
复制标题
四个顶点上的根拓扑次要
DOI：
10.1016/j.jctb.2021.05.002
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Ken-ichi Kawarabayashi
中科院分区：
文献类型：
--
作者：
Koyo Hayashi;Ken-ichi Kawarabayashi
对于图G和G的四个不同顶点的集合Z，Z上的菱形是G的一个子图，使得对于某个标号Z={v1，v2，v3，v4}，存在三条内部不交的路P1，P2，P3，它们的端点分别为v1，v2和v3，v4.因此，这会产生一个K 4−-细分，其分支顶点位于Z上。我们刻画了在一个给定的四顶点集Z上不含菱形的图G，假设对每个v∈ Z，G有三条从v到Z−{v}的路，除了v之外，它们相互不相交。我们的证明是基于马德尔的S-路径定理。
For a graph G and a set Z of four distinct vertices of G, a diamond on Z is a subgraph of G such that, for some labeling Z={v 1, v 2, v 3, v 4}, there are three internally disjoint paths P 1, P 2, P 3 with end vertices v 1, v 2 with v 3, v 4 on P 1, P 2, respectively. Therefore, this yields a K 4−-subdivision with branch vertices on Z. We characterize graphs G that contain no diamond on a prescribed set Z of four vertices, under the assumption that for every v∈ Z there are three paths of G from v to Z−{v}, mutually disjoint except for v. Moreover, we can find two “different” such subdivisions, if one exists. Our proof is based on Mader's S-paths theorem.