✦ LIBER ✦

Removable edges in 3-connected graphs

✍ Scribed by Derek A. Holton; Bill Jackson; Akira Saito; Nicholas C. Wormald

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

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An edge e of a 3‐connected graph G is said to be removable if G ‐ e is a subdivision of a 3‐connected graph. If e is not removable, then e is said to be nonremovable. In this paper, we study the distribution of removable edges in 3‐connected graphs and prove that a 3‐connected graph of order n ≥ 5 has at most [(4 n — 5)/3] nonremovable edges.

📜 SIMILAR VOLUMES

The Number of Removable Edges in 3-Conne

The Number of Removable Edges in 3-Connected Graphs

✍ Su Jianji 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 147 KB

An edge of a 3-connected graph G is said to be removable if G&e is a subdivision of a 3-connected graph. Holton et al. (1990) proved that every 3-connected graph of order at least five has at least W(|G| +10)Â6X removable edges. In this paper, we prove that every 3-connected graph of order at least

Contractible Non-edges in 3-Connected Gr

Contractible Non-edges in 3-Connected Graphs

✍ Matthias Kriesell 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 495 KB

We present a reduction theorem for the class of all finite 3-connected graphs which does not make use of the traditional contraction of certain connected subgraphs. ## 1998 Academic Press Contractible edges play an important role in the theory of 3-connected graphs. Besides the famous wheel theore

Longest cycles in 3-connected graphs con

Longest cycles in 3-connected graphs contain three contractible edges

✍ Nathaniel Dean; Robert L. Hemminger; Katsuhiro Ota 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB 👁 1 views

We show that if G is a 3-connected graph of order at least seven, then every longest path between distinct vertices in G contains at least two contractible edges. An immediate corollary is that longest cycles in such graphs contain at least three contractible edges. We consider only finite undirect

Contractible Edges and Triangles in k-Co

Contractible Edges and Triangles in k-Connected Graphs

✍ Ken-ichi Kawarabayashi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 129 KB

It is proved that if G is a k-connected graph which does not contain K - 4 , then G has an edge e or a triangle T such that the graph obtained from G by connecting e or by contracting T is still k-connected. By using this theorem, we prove some theorems which are generalizations of earlier work. In

Eulerian subgraphs in 3-edge-connected g

Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs

✍ Zhi-Hong Chen; Hong-Jian Lai; Xiangwen Li; Deying Li; Jinzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

## Abstract In this paper, we show that if __G__ is a 3‐edge‐connected graph with $S \subseteq V(G)$ and $|S| \le 12$, then either __G__ has an Eulerian subgraph __H__ such that $S \subseteq V(H)$, or __G__ can be contracted to the Petersen graph in such a way that the preimage of each vertex of th

Edge-connectivity in p-partite graphs

✍ Lutz Volkmann 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB

Let G = (V, €1 be a finite, simple p-partite graph with minimum degree 6 and edge-connectivity A. It is proved that if IVI d (2pS)/(p -1) -2 or in special cases that if IVI I ( 2 p 6 ) / ( p -1) -1, then A = S . It is further shown that this result is best possible.