Contractible subgraphs in k‐connected graphs
Contractible subgraphs in k‐connected graphs
复制标题
k连通图中的可收缩子图
DOI：
10.1002/jgt.20227
复制
发表时间：
2007
影响因子：
0.9
通讯作者：
Xiaoyan Zhang
中科院分区：
文献类型：
--
作者：
Zemin Jin;Xingxing Yu;Xiaoyan Zhang
对于图G，我们定义了一个图T(G)，它的顶点是G中的三角形，且T(G)的两个顶点是相邻的，如果它们在G中对应的三角形共享一条边。Kawa abayashi证明了：如果G是k-连通图，且T(G)不含边，则G至多有一个k-可缩团，其规模至多为3，推广了Thomassen的一个结果。本文进一步推广了Kawa abayashi的结果，证明了如果G是k-连通的，且T(G)的最大次数至多为1，则G至多有一个大小为3的k-可缩团，或者G存在独立的边e和f，使得e和f包含在共享一条边的三角形中，且G/e/f是k-连通的。©2006威利期刊公司.图论杂志55：121-136,2007
For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007
图具有 κ 可收缩边的一些禁止子图条件
DOI：
--
发表时间：
2003
期刊：
Discrete Math. 267, no.1-3
影响因子：
--
作者：
Ando;Kiyoshi;Kawarabayashi;Ken-ichi
通讯作者：
Ken-ichi
k 连接图中的可收缩边和三角形
DOI：
--
发表时间：
2002
期刊：
J.Combin. Theory Ser.B 85,no.2
影响因子：
--
作者：
K.Kawarabayashi;A.Nakamoto;Y.Oda;K.Ota;S.Tazawa;M.Watanabe;K.Kawarabayashi
通讯作者：
K.Kawarabayashi