𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Long cycles in triangle-free graphs with prescribed independence number and connectivity

✍ Scribed by Hikoe Enomoto; Atsushi Kaneko; Akira Saito; Bing Wei

Book ID
108167356
Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
263 KB
Volume
91
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Long cycles in graphs with prescribed to
Long cycles in graphs with prescribed toughness and minimum degree
✍ Douglas Bauer; H.J. Broersma; J. van den Heuvel; H.J. Veldman πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 427 KB

A cycle C of a graph G is a D~-cycle if every component of G-V(C) has order less than 2. Using the notion of D~-cycles, a number of results are established concerning long cycles in graphs with prescribed toughness and minimum degree. Let G be a t-tough graph on n/> 3 vertices. If 6 > n/(t + 2) + 2-

Size and independence in triangle-free g
Size and independence in triangle-free graphs with maximum degree three
✍ Kathryn Fraughnaugh Jones πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 549 KB

## Abstract Let __C__ be the class of triangle‐free graphs with maximum degree at most three. A lower bound for the number of edges in a graph of __C__ is derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As coroll

Edge density and independence ratio in t
Edge density and independence ratio in triangle-free graphs with maximum degree three
✍ Jerrold Griggs; Owen Murphy πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 548 KB

A simple polynomial-time algorithm is presented which computes independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. Let nand m denote the number of vertices and edges, respectively, and let c '= m/n denote the edge density where c < 3/2. The algorithm