图中的圈不可分离性(英文)

Cyclic separability in graphs

如果对图中的两条边或两个顶点,存在两个顶点不交圈分别包含他们,那么这两条边或两个顶点叫做可用圈分离。不能用圈分离的边对或点对叫做圈不可分离的。定义了包含一对不可用圈分离的边的图的一个无穷类。给出了两个顶点或两条边不可用圈分离的一个简单的充分条件。这个无穷类包含Wagner图作为元素。提出了关于所定义的概念和图类的一些尚未解决的研究问题。

For a pair of edges or vertices in a graph, if there exist vertex disjoint cycles in the graph such that the two members are contained in different cycles, then the pair is called cyclically separable. If two edges or vertices are not cyclically separable then they are called cyclically inseparable. An infinite family of graphs that contain a pair of cyclically inseparable edges is defined, and a simple sufficient con- dition for a pair of vertices or a pair of edges to be cyclically inseparable are established. The family con- tains all Wagner graphs as members. A few problems arising from this study are proposed.