𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum acyclic and fragmented sets in regular graphs

✍ Scribed by Penny Haxell; Oleg Pikhurko; Andrew Thomason

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
126 KB
Volume
57
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We show that a typical d‐regular graph G of order n does not contain an induced forest with around ${2 {\rm In} d \over d}$ vertices, when n ≫ d ≫ 1, this bound being best possible because of a result of Frieze and Łuczak [6]. We then deduce an affirmative answer to an open question of Edwards and Farr (see [4]) about fragmentability, which concerns large subgraphs with components of bounded size. An alternative, direct answer to the question is also given. Β© 2007 Wiley Periodicals, Inc. J Graph Theory 57: 149–156, 2008

πŸ“œ SIMILAR VOLUMES

Signed Domination in Regular Graphs and
Signed Domination in Regular Graphs and Set-Systems
✍ ZoltΓ‘n FΓΌredi; Dhruv Mubayi πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 188 KB

Suppose G is a graph on n vertices with minimum degree r. Using standard random methods it is shown that there exists a two-coloring of the vertices of G with colors, +1 and &1, such that all closed neighborhoods contain more 1's than &1's, and all together the number of 1's does not exceed the numb

Independent Dominating Sets and a Second
Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs
✍ Carsten Thomassen πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 241 KB

In 1975, John Sheehan conjectured that every Hamiltonian 4-regular graph has a second Hamiltonian cycle. Combined with earlier results this would imply that every Hamiltonian r-regular graph (r 3) has a second Hamiltonian cycle. We shall verify this for r 300.

Maximal and maximum independent sets in
Maximal and maximum independent sets in graphs with at most r cycles
✍ Bruce E. Sagan; Vincent R. Vatter πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 236 KB πŸ‘ 2 views

## Abstract Let __m__(__G__) denote the number of maximal independent sets of vertices in a graph __G__ and let __c__(__n__,__r__) be the maximum value of __m__(__G__) over all connected graphs with __n__ vertices and at most __r__ cycles. A theorem of Griggs, Grinstead, and Guichard gives a formul

Acyclic edge coloring of graphs with max
Acyclic edge coloring of graphs with maximum degree 4
✍ Manu Basavaraju; L. Sunil Chandran πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 168 KB πŸ‘ 1 views

## Abstract An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__β€²(__G__). It was conj

Tutte sets in graphs I: Maximal tutte se
Tutte sets in graphs I: Maximal tutte sets and D-graphs
✍ D. Bauer; H. J. Broersma; A. Morgana; E. Schmeichel πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 177 KB

## Abstract A well‐known formula of Tutte and Berge expresses the size of a maximum matching in a graph __G__ in terms of what is usually called the deficiency of __G__. A subset __X__ of __V__(__G__) for which this deficiency is attained is called a Tutte set of __G__. While much is known about ma