𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Size and independence in triangle-free graphs with maximum degree three

✍ Scribed by Kathryn Fraughnaugh Jones

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
549 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 corollaries, we obtain the best possible lower bound for the independence ratio of a graph in C and evaluate some Ramsey‐type numbers.

πŸ“œ SIMILAR VOLUMES

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

Largest bipartite subgraphs in triangle-
Largest bipartite subgraphs in triangle-free graphs with maximum degree three
✍ J. A. Bondy; S. C. Locke πŸ“‚ Article πŸ“… 1986 πŸ› John Wiley and Sons 🌐 English βš– 977 KB

Let G be a triangle-free, loopless graph with maximum degree three. We display a polynomi$ algorithm which returns a bipartite subgraph of G containing at least 5 of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3-regular, triangle-free, loopless, c

Degree sequence and independence in K(4)
Degree sequence and independence in K(4)-free graphs
✍ Paul ErdΕ‘s; Ralph Faudree; Talmage James Reid; Richard Schelp; William Staton πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 268 KB

We investigate whether K,-free graphs with few repetitions in the degree sequence may have independence number o(n). We settle the cases r = 3 and r >/5, and give partial results for the very interesting case r=4. In an earlier article I-4] it is shown that triangle-free graphs in which no term of

Size in maximal triangle-free graphs and
Size in maximal triangle-free graphs and minimal graphs of diameter 2
✍ Curtiss Barefoot; Karen Casey; David Fisher; Kathryn Fraughnaugh; Frank Harary πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 290 KB

A triangle-free graph is maximal if the addition of any edge creates a triangle. For n ~> 5, we show there is an n-node m-edge maximal triangle-free graph if and only if it is complete bipartite or 2n-5<<.m<<.L(n-1)2/4J+l. A diameter 2 graph is minimal if the deletion of any edge increases the diame