✦ LIBER ✦

The Connectivities of Leaf Graphs of 2-Connected Graphs

✍ Scribed by Atsushi Kaneko; Kiyoshi Yoshimoto

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 286 KB
Volume: 76
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1895

No coin nor oath required. For personal study only.

✦ Synopsis

Given a connected graph G, denote by V the family of all the spanning trees of G. Define an adjacency relation in V as follows: the spanning trees t and t$ are said to be adjacent if for some vertex u # V, t&u is connected and coincides with t$&u. The resultant graph G is called the leaf graph of G. The purpose of this paper is to show that if G is 2-connected with minimal degree $, then G is (2$&2)-connected.

📜 SIMILAR VOLUMES

On k-leaf connectivity of a random graph

✍ Thomasz Luczak 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB

We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > f . A threshold function for k-leaf connectivity is also found. ## 1. MAIN RESULTS Let G = (V(G),E(G)) be a graph, where V (

2-Connected Spanning Subgraphs of Planar

2-Connected Spanning Subgraphs of Planar 3-Connected Graphs

✍ D.W. Barnette 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 278 KB

We prove that every planar 3-connected graph has a 2-connected spanning subgraph of maximum valence 15 . We give an example of a planar 3 -connected graph with no spanning 2-connected subgraph of maximum valence five. i) 1994 Academic Press, Inc.

Minimally 2-edge connected graphs

✍ G. Chaty; M. Chein 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 338 KB

## Abstract A constructive characterization of minimally 2‐edge connected graphs, similar to those of Dirac for minimally 2‐connected graphs is given.

All 4-connected Line Graphs of Claw Free

All 4-connected Line Graphs of Claw Free Graphs Are Hamiltonian Connected

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 109 KB

Thomassen conjectured that every 4-connected line graph is hamiltonian. Here we shall see that 4-connected line graphs of claw free graphs are hamiltonian connected.

2-connected 7-coverings of 3-connected g

2-connected 7-coverings of 3-connected graphs on surfaces

✍ Ken-ichi Kawarabayashi; Atsuhiro Nakamoto; Katsuhiro Ota 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

## Abstract An __m__‐__covering__ of a graph __G__ is a spanning subgraph of __G__ with maximum degree at most __m__. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus __k__ ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most

The rainbow connectivity of a graph

✍ Gary Chartrand; Garry L. Johns; Kathleen A. McKeon; Ping Zhang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB