New results on large induced forests in graphs
S Kogan - arXiv preprint arXiv:1910.01356, 2019 - arxiv.org
arXiv preprint arXiv:1910.01356, 2019•arxiv.org
For a graph $ G $, let $ a (G) $ denote the maximum size of a subset of vertices that induces
a forest. We prove the following. 1. Let $ G $ be a graph of order $ n $, maximum degree
$\Delta> 0$ and maximum clique size $\omega $. Then\[a (G)\geq\frac
{6n}{2\Delta+\omega+ 2}.\] This bound is sharp for cliques. 2. Let $ G=(V, E) $ be a triangle-
free graph and let $ d (v) $ denote the degree of $ v\in V $. Then\[a (G)\geq\sum_ {v\in
V}\min\left (1,\frac {3}{d (v)+ 2}\right).\] As a corollary we have that a triangle-free graph $ G …
a forest. We prove the following. 1. Let $ G $ be a graph of order $ n $, maximum degree
$\Delta> 0$ and maximum clique size $\omega $. Then\[a (G)\geq\frac
{6n}{2\Delta+\omega+ 2}.\] This bound is sharp for cliques. 2. Let $ G=(V, E) $ be a triangle-
free graph and let $ d (v) $ denote the degree of $ v\in V $. Then\[a (G)\geq\sum_ {v\in
V}\min\left (1,\frac {3}{d (v)+ 2}\right).\] As a corollary we have that a triangle-free graph $ G …
For a graph , let denote the maximum size of a subset of vertices that induces a forest. We prove the following. 1. Let be a graph of order , maximum degree and maximum clique size . Then
This bound is sharp for cliques. 2. Let be a triangle-free graph and let denote the degree of . Then
As a corollary we have that a triangle-free graph of order , with edges and average degree satisfies
This improves the lower bound of Alon-Mubayi-Thomas for graphs of average degree greater than . Furthermore it improves the lower bound of Shi-Xu for (connected) graphs of average degree at least .
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果