Cycles through specified vertices of a graph
Cycles through specified vertices of a graph
复制标题
循环遍历图的指定顶点
DOI：
10.1007/bf02579268
复制
发表时间：
1981
期刊：
影响因子：
1.1
通讯作者：
L. Lovász
中科院分区：
文献类型：
--
作者：
J. Bondy;L. Lovász
证明了：如果S是k-连通图G中k-1个顶点的集合，则通过S的圈生成G的圈空间.当k ≥ 3时，G的每个圈都可以表示为通过S的奇数个圈之和.另一方面，如果是k个顶点的集合，这些结论不一定成立，我们刻画了例外情况。作为推论，我们建立了通过指定顶点的奇圈和偶圈的存在性，并推导出了高连通图中长奇圈和长偶圈的存在性。
We prove that ifSis a set ofk−1 vertices in ak-connected graphG, then the cycles throughSgenerate the cycle space ofG. Moreover, whenk≧3, each cycle ofGcan be expressed as the sum of an odd number of cycles throughS. On the other hand, ifSis a set ofkvertices, these conclusions do not necessarily hold, and we characterize the exceptional cases. As corollaries, we establish the existence of odd and even cycles through specified vertices and deduce the existence of long odd and even cycles in graphs of high connectivity.