𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Separation of graphs into three components by the removal of edges

✍ Scribed by Donald L. Goldsmith; Bennet Manvel; Vance Faber

Publisher
John Wiley and Sons
Year
1980
Tongue
English
Weight
266 KB
Volume
4
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Several ways to separate a connected graph into three components by the removal of edges are discussed. Graphical parameters that count the number of edges removed are introduced and the relations between these parameters are given.

πŸ“œ 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

Covering the Edges of a Connected Graph
Covering the Edges of a Connected Graph by Paths
✍ L. Pyber πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 316 KB

We prove that every connected graph on n vertices can be covered by at most nΓ‚2+O(n 3Γ‚4 ) paths. This implies that a weak version of a well-known conjecture of Gallai is asymptotically true.

Covering the Edges of a Graph by a Presc
Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap
✍ Noga Alon; Yair Caro; Raphael Yuster πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 360 KB

Let H=(V H , E H ) be a graph, and let k be a positive integer. A graph G=(V G , E G ) is H-coverable with overlap k if there is a covering of the edges of G by copies of H such that no edge of G is covered more than k times. Denote by overlap(H, G) the minimum k for which G is H-coverable with over