✦ LIBER ✦

Covering contractible edges in 3-connected graphs. I: Covers of size three are cutsets

✍ Scribed by Akira Saito

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 397 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140603

No coin nor oath required. For personal study only.

✦ Synopsis

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 contractible edges in a 3‐connected graph cannot be covered by two vertices, and extended this result to a three‐vertex covering. We also study the existence of a contractible edge whose contraction preserves a specified cycle, and show that a non‐hamiltonian 3‐connected graph has a contractible edge whose contraction preserves the circumference.

📜 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.

3-connected graphs with non-cut contract

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

✍ Xingxing Yu 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 493 KB 👁 1 views

## 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