On cycles through prescribed vertices in weakly separable graphs

✍ Scribed by A.K. Kelmans; M.V. Lomonosov

• Publisher: Elsevier Science
• Year: 1983
• Tongue: English
• Weight: 275 KB
• Volume: 46
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(83)90251-0

✦ Synopsis

Notions and notations 1.1. Given an undirected graph G let V(G), E(G), K(G) and comp(G) denote the vertex-set, edge-set, vertex connectivity and number of components of G, respectively. Put P(G)={(X, Y): X~V(G), Tc\E(G--X)}. For X~V(G) let G(X) denote the induced suL\*graph. For Y :\ E(G) let G(Y) denote the subgraph of G with the edge-set Y and without isolated vertices.
Given
1.2. For Y~E(G) let OY denote the set of vertices covered by both Y and E(G)-Y, and pu~ CG(Y)= Y.s/) JOGYsl/ with the summation over all components of G(Y), Y~ being the edge-set of the sth component. For (X, Y)~-P
Previous results

2

.1. Clearly G cannot have both a T-cycle and a T-separator. 2.2. In [4] the following "cycle-separator' alternative is established. "I'neorem. Let G be k-connected, k !>2, Tc V(G), ITl~~3. Then G has a T-cycle if and only if G has no T-separalor.