𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Average degree and contractibility

✍ Scribed by Matthias Kriesell

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
197 KB
Volume
51
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved that for every number k there exists a number f (k) such that every finite k-connected graph of average degree exceeding f (k) contains an edge whose contraction yields again a k-connected graph. For the proof, tree orders on certain sets of smallest separating sets of the graph in question are constructed. This leads to new canonical tree decompositions as well.

πŸ“œ SIMILAR VOLUMES

Independence, odd girth, and average deg
Independence, odd girth, and average degree
✍ Christian LΓΆwenstein,; Anders Sune Pedersen,; Dieter Rautenbach;; Friedrich Rege πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 187 KB

We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle-free graphs of maximum degree a

Average distance, minimum degree, and sp
Average distance, minimum degree, and spanning trees
✍ Dankelmann, Peter; Entringer, Roger πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 218 KB

The average distance Β΅(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., Β΅(G) = ( n 2 ) -1 {x,y}βŠ‚V (G) d G (x, y), where V (G) denotes the vertex set of G and d G (x, y) is the distance between x and y. We prove that every connected graph

Improper choosability of graphs and maxi
Improper choosability of graphs and maximum average degree
✍ FrΓ©dΓ©ric Havet; Jean-SΓ©bastien Sereni πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 174 KB

## Abstract Improper choosability of planar graphs has been widely studied. In particular, Ε krekovski investigated the smallest integer __g__~k~ such that every planar graph of girth at least __g__~k~ is __k__‐improper 2‐choosable. He proved [9] that 6 ≀ __g__~1~ ≀ 9; 5 ≀  __g__~2~ ≀ 7; 5 ≀ __g__~3

Contractibility and NP-completeness
Contractibility and NP-completeness
✍ A. E. Brouwer; H. J. Veldman πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 344 KB
Decomposition-enhanced spike-triggered a
Decomposition-enhanced spike-triggered averaging: Contraction level effects
✍ Robin A. Conwit; Brian Tracy; Chris Jamison; Megan Mchugh; Dan Stashuk; William πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

Decomposition-enhanced spike-triggered averaging (DE-STA) was applied to the vastus medialis muscle to examine size distributions of surface-detected motor unit action potentials (S-MUAPs) at various force levels. Using DE-STA, 15-20 S-MUAPs were identified during 5%, 10%, 20%, and 30% of maximum vo