✦ LIBER ✦

A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph

✍ Scribed by Kenta Ozeki; Tomoki Yamashita

Publisher: Springer Japan
Year: 2008
Tongue: English
Weight: 200 KB
Volume: 24
Category: Article
ISSN: 0911-0119
DOI: 10.1007/s00373-008-0802-z

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A Short Proof of a Theorem Concerning De

A Short Proof of a Theorem Concerning Degree Sums and Connectivity on Hamiltonian Graphs

✍ Bing Wei 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 74 KB

proved that if G is a 2-connected graph with n vertices such that d(u)+d(v)+d(w) n+} holds for any triple of independent vertices u, v, and w, then G is hamiltonian, where } is the vertex connectivity of G. In this note, we will give a short proof of the above result.

On the sum of two parameters concerning

On the sum of two parameters concerning independence and irredundance in a graph

✍ Chengde Wang 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 398 KB

A Degree Sum Condition for the Existence

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

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

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

The number of maximal independent sets i

The number of maximal independent sets in a connected graph

✍ Jerrold R. Griggs; Charles M. Grinstead; David R. Guichard 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 1021 KB

We determine the maximum on n vertices can have, and we a question of Wilf. number of maximal independent sets which a connected graph completely characterize the extremal graphs, thereby answering \* Partially supported by NSF grant number DIMS-8401281. t Partially supported by NSF grant number D S

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