✦ LIBER ✦

Generalized degree conditions for graphs with bounded independence number

✍ Scribed by Ralph Faudree; Ronald J. Gould; Linda Lesniak; Terri Lindquester

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 511 KB
Volume: 19
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190190312

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac-type bound on this degree in conjunction with a bound on the independence number of a graph is sufficient to imply certain hamiltonian properties in graphs. For K,,,,-free graphs we obtain generalizations of known results. In particular we show:

Theorem. Let r 2 1 and rn 2 3 be integers. Then for each nonnegative function f(r, rn) there exists a constant

📜 SIMILAR VOLUMES

Total interval number for graphs with bo

Total interval number for graphs with bounded degree

✍ Kostochka, Alexander V.; West, Douglas B. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 2 views

The total interval number of an n-vertex graph with maximum degree ∆ is at most (∆+1/∆)n/2, with equality if and only if every component of the graph is K ∆,∆ . If the graph is also required to be connected, then the maximum is ∆n/2 + 1 when ∆ is even, but when ∆ is odd it exceeds [∆ + 1/(2.5∆ + 7.7

On Induced Ramsey Numbers for Graphs wit

On Induced Ramsey Numbers for Graphs with Bounded Maximum Degree

✍ Tomasz Łuczak; Vojtěch Rödl 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 435 KB

For graphs G and H we write G wÄ ind H if every 2-edge colouring of G yields an induced monochromatic copy of H. The induced Ramsey number for H is defined as r ind (H)=min[ |V(G)|: G wÄ ind H]. We show that for every d 1 there exists an absolute constant c d such that r ind (H n, d ) n cd for every

On independent generalized degrees and i

On independent generalized degrees and independence numbers in K(1, m)-free graphs

✍ R.J. Faudree; R.J. Gould; M.S. Jacobson; L.M. Lesniak; T.E. Lindquester 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 427 KB

Minimum independent generalized t-degree

Minimum independent generalized t-degree and independence number in K1,r+1-free graphs

✍ O. Favaron; Y. Redouane 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 448 KB

The minimum independent generalized t-degree of a graph G = (V,E) is ut = min{ IN(H H is an independent set of t vertices of G}, with N(H) = UxtH N(x). In a KI,~+I -free graph, we give an upper bound on u! in terms of r and the independence number CI of G. This generalizes already known results on u

On the independent domination number of

On the independent domination number of graphs with given minimum degree

✍ N.I. Glebov; A.V. Kostochka 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 175 KB

We prove a new upper bound on the independent domination number of graphs in terms of the number of vertices and the minimum degree. This bound is slightly better than that of Haviland (1991) and settles the case 6 = 2 of the corresponding conjecture by Favaron (1988). @ 1998 Elsevier Science B.V. A

A local independence number condition fo

A local independence number condition for n-extendable graphs

✍ Dingjun Lou 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 273 KB

Let G be a graph and v C V(G). Let Nk(v)= {ulu C V(G) and d(u, v)= k}. It is proved that if G is a connected graph with oo>9(G)~>4 and with even order and if, for each vertex is regular and rd(v)/4]-extendable. All results in this paper are sharp. (~) 1999 Elsevier Science B.V. All rights reserved