๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Rooted induced trees in triangle-free graphs

โœ Scribed by Florian Pfender

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
68 KB
Volume
64
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

Abstract

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of __G__that is a tree. Further, for a vertex vโˆˆV(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of __G__that is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangleโ€free graphs G(and vertices vโˆˆV(G)) on __n__vertices is denoted by t~3~(n) (t(n)). Clearly, t(G, v)โฉฝt(G) for all vโˆˆV(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that __G__is connected and triangleโ€free. We show that
and determine the unique extremal graphs. Thus, we get as corollary that \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}$t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$\end{document}, improving a recent result by Fox, Loh and Sudakov. ยฉ 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206โ€“209, 2010

๐Ÿ“œ SIMILAR VOLUMES

2-factors in triangle-free graphs
2-factors in triangle-free graphs
โœ Bauer, D.; van den Heuvel, J.; Schmeichel, E. ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 440 KB ๐Ÿ‘ 3 views

We study the cycle structure of I-tough, triangle-free graphs. In particular, w e prove that every such graph on n 2 3 vertices with minimum degree 6 2 i ( n + 2) has a 2-factor. W e also show this is best possible by exhibiting an infinite class of I-tough, triangle-free graphs having 6 = $ ( n + 1

Induced trees in graphs of large chromat
Induced trees in graphs of large chromatic number
โœ Scott, A. D. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 134 KB ๐Ÿ‘ 2 views

Gyรกrfรกs and Sumner independently conjectured that for every tree T and integer k there is an integer f (k, T ) such that every graph G with ฯ‡(G) > f(k, t) contains either K k or an induced copy of T . We prove a `topologicalยดversion of the conjecture: for every tree T and integer k there is g(k, T )

Recognizing triangle-free graphs with in
Recognizing triangle-free graphs with induced path-cycle double covers is NP-complete
โœ Jacobson, Michael S.; K๏ฟฝzdy, Andr๏ฟฝ E.; Lehel, Jen? ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 250 KB ๐Ÿ‘ 2 views

An induced path-cycle double cover (IPCDC) of a simple graph G is a family F ร… {F 1 , . . . , F k } of induced paths and cycles of G such that if F i ส F j x M, then F i ส F j is a vertex or an edge, for i x j, each edge of G appears in precisely two of the F i 's, and each vertex of G appears in pr

The largest induced tree in a sparse ran
The largest induced tree in a sparse random graph
โœ W. Fernandez de la Vega ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 192 KB ๐Ÿ‘ 2 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar