𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Degree Sum Condition for the Existence of a Contractible Edge in a κ-Connected Graph

✍ Scribed by Matthias Kriesell

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
184 KB
Volume
82
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

It is known that a noncomplete }-connected graph of minimum degree of at least w 5} 4 x contains a }-contractible edge, i.e., an edge whose contraction yields again a }-connected graph. Here we prove the stronger statement that a noncomplete }-connected graph for which the sum of the degrees of any two distinct vertices is at least 2 w 5 4 }x&1 possesses a }-contractible edge. The bound is sharp and remains valid and sharp if we look only at degree sums at pairs of vertices at distances of one or two, provided that }{7.

📜 SIMILAR VOLUMES

A degree sum condition for longest cycle
A degree sum condition for longest cycles in 3-connected graphs
✍ Tomoki Yamashita 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 1 views

## Abstract For a graph __G__, we denote by __d__~__G__~(__x__) and κ(__G__) the degree of a vertex __x__ in __G__ and the connectivity of __G__, respectively. In this article, we show that if __G__ is a 3‐connected graph of order __n__ such that __d__~__G__~(__x__) + __d__~__G__~(__y__) + __d__~__

A sufficient condition for equality of e
A sufficient condition for equality of edge-connectivity and minimum degree of a graph
✍ Donald L. Goldsmith; Roger C. Entringer 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract Let __G__ be a connected graph of order __p__ ≥ 2, with edge‐connectivity κ~1~(__G__) and minimum degree δ(__G__). It is shown her ethat in order to obtain the equality κ~1~(__G__) = δ(__G__), it is sufficient that, for each vertex __x__ of minimum degree in __G__, the vertices in the n

A degree condition for the circumference
A degree condition for the circumference of a graph
✍ Nathaniel Dean; Pierre Fraisse 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 1 views

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let rn be any positive integer. Suppose G is a 2-connected graph with vertices x,, . . . , x, and edge set E that satisfies the proper

A degree condition for the existence of
A degree condition for the existence of k-factors
✍ Tsuyoshi Nishimura 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 358 KB 👁 1 views

## Abstract Let __k__ be an integer such that ≦, and let __G__ be a connected graph of order __n__ with ≦, __kn__ even, and minimum degree at least __k__. We prove that if __G__ satisfies max(deg(u), deg(v)) ≦ n/2 for each pair of nonadjacent vertices __u, v__ in __G__, then __G__ has a __k__‐facto