𝔖 Bobbio Scriptorium
✦   LIBER   ✦

3-connected graphs with non-cut contractible edge covers of size k

✍ Scribed by Xingxing Yu

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
493 KB
Volume
18
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper, we show that if a 3‐connected graph G other than K~4~ has a vertex subset K that covers the set of contractible edges of G and if |K| 3 and |V(G)| 3|K| − 1, then K is a cutset of G. We also give examples to show that this result is best possible. In particular, the result does not hold for K with smaller cardinality.

📜 SIMILAR VOLUMES

Covering contractible edges in 3-connect
Covering contractible edges in 3-connected graphs. II. Characterizing those with covers of size three
✍ Robert L. Hemminger; Xingxing Yu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 1 views

## Abstract It is shown that if __G__ is a 3‐connected graph with |__V(G)__| ≥ 10, then, with the exception of one infinite class based on __K__~3,__p__~, it takes at least four vertices to cover the set of contractible edges of __G__. © 1993 John Wiley & Sons, Inc.

Covering contractible edges in 3-connect
Covering contractible edges in 3-connected graphs. I: Covers of size three are cutsets
✍ Akira Saito 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 397 KB 👁 1 views

## Abstract An edge of a 3‐connected graph is said to be __contractible__ if its contraction results in a 3‐connected graph. In this paper, a covering of contractible edges is studied. We give an alternative proof to the result of Ota and Saito (__Scientia__ (A) 2 (1988) 101–105) that the set of co