𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on a conjecture about cycles with many incident chords

✍ Scribed by Tao Jiang

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
44 KB
Volume
46
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given positive integers n and k, let g~k~(n) denote the maximum number of edges of a graph on n vertices that does not contain a cycle with k chords incident to a vertex on the cycle. BollobΓ‘s conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function n(k) such that g~k~(n) = (k + 1)nβ€‰βˆ’β€‰(k + 1)^2^ for all n β‰₯ n(k). Using an old result of Bondy [3], we prove the conjecture, showing that n(k) ≀ 3 k + 3. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 46: 180–182, 2004

πŸ“œ SIMILAR VOLUMES

On a Conjecture about Trees in Graphs wi
On a Conjecture about Trees in Graphs with Large Girth
✍ Tao Jiang πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 169 KB

The girth of a graph G is the length of a shortest cycle in G. Dobson (1994, Ph.D. dissertation, Louisiana State University, Baton Rouge, LA) conjectured that every graph G with girth at least 2t+1 and minimum degree at least kΓ‚t contains every tree T with k edges whose maximum degree does not excee

On a Conjecture of Bannai and Ito: There
On a Conjecture of Bannai and Ito: There are Finitely Many Distance-regular Graphs with Degree 5, 6 or 7
✍ J.H. Koolen; V. Moulton πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 312 KB

Bannai and Ito conjectured in a 1987 paper that there are finitely many distance-regular graphs with fixed degree that is greater than two. In a series of papers they showed that their conjecture held for distance-regular graphs with degrees 3 or 4. In this paper we prove that the Bannai-Ito conject

Short Communication: A note on optimal h
Short Communication: A note on optimal hybrid V-cycle multilevel algorithms for mixed finite element systems with penalty term
✍ Chen-Yao G. Lai πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 74 KB πŸ‘ 3 views

In this paper, we investigate some cost-effective hybrid V -cycle multilevel algorithms for the discrete systems that arise when a mixed finite element approach is used to solve certain second-order elliptic boundary value problems. By introducing a small penalty parameter, the perturbed indefinite