Independence number and disjoint theta graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a $\theta$-graph to be a pair of vertices $u, v$ with three internally disjoint paths joining $u$ to $v$. Given an independence number $\alpha$ and a fixed integer $k$, the results contained in this paper provide sharp bounds on the order $f(k, \alpha)$ of a graph with independence number $\alpha(G) \leq \alpha$ which contains no $k$ disjoint $\theta$-graphs. Since every $\theta$-graph contains an even cycle, these results provide $k$ disjoint even cycles in graphs of order at least $f(k, \alpha) + 1$. We also discuss the relationship between this problem and a generalized ramsey problem involving sets of graphs.
@article{10_37236_637,
author = {Shinya Fujita and Colton Magnant},
title = {Independence number and disjoint theta graphs},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/637},
zbl = {1222.05114},
url = {http://geodesic.mathdoc.fr/articles/10.37236/637/}
}
Shinya Fujita; Colton Magnant. Independence number and disjoint theta graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/637
Cité par Sources :