𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On-line connectivity algorithms

✍ Scribed by Grant A. Cheston

Publisher
John Wiley and Sons
Year
1984
Tongue
English
Weight
615 KB
Volume
14
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On hamiltonian line graphs and connectiv
On hamiltonian line graphs and connectivity
✍ Siming Zhan πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 444 KB

A well-known conjecture of Thomassen says that every 4-connected line graph is hamiltonian. In this paper we prove that every 7-connected line graph is hamiltonian-connected. For line graph, C. Thomassen [l] made the following conjecture. Conjecture. Every 4-connected line graph is hamiltonian.

Optimal on-line decremental connectivity
Optimal on-line decremental connectivity in trees
✍ Stephen Alstrup; Jens Peter Secher; Maz Spork πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 310 KB

Let T be a tree with n nodes from which edges are deleted interspersed with m on-line connectivity queries. Even and Shiloach gave an 0( n log n + m) algorithm to process edge deletion and m queries (Even and Shiloach, 1981). In this paper we present an O(n + m) algorithm for the same problem. @ 199

Graphs with prescribed connectivity and
Graphs with prescribed connectivity and line graph connectivity
✍ Douglas Bauer; Ralph Tindell πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 118 KB

## Abstract Chartrand and Stewart have shown that the line graph of an __n__‐connected graph is itself __n__‐connected. This paper shows that for every pair of integers __m__ > __n__ > 1 there is a graph of point connectivity __n__ whose line graph has point connectivity __m__. The corresponding qu