Polarities and 2k-cycle-free graphs

F Lazebnik, VA Ustimenko, AJ Woldar - Discrete Mathematics, 1999 - Elsevier
Discrete Mathematics, 1999Elsevier
Let C2k be the cycle on 2k vertices, and let ex (v, C2k) denote the greatest number of edges
in a simple graph on v vertices which contains no subgraph isomorphic to C2k. In this paper
we discuss a method which allows one to sometimes improve numerical constants in lower
bounds for ex (v, C2k). The method utilizes polarities in certain rank two geometries. It is
applied to refute some conjectures about the values of ex (v, C2k), and to construct some
new examples of graphs having certain restrictions on the lengths of their cycles. In …
Let C2k be the cycle on 2k vertices, and let ex(v, C2k) denote the greatest number of edges in a simple graph on v vertices which contains no subgraph isomorphic to C2k. In this paper we discuss a method which allows one to sometimes improve numerical constants in lower bounds for ex(v, C2k). The method utilizes polarities in certain rank two geometries. It is applied to refute some conjectures about the values of ex(v, C2k), and to construct some new examples of graphs having certain restrictions on the lengths of their cycles. In particular, we construct an infinite family {Gi} of C6-free graphs with |E(G i)| ∼ 1 2 |V(G i)| 4 3 , i → ∞ , which improves the constant in the previous best lower bound on ex(v, C6) from 2 3 4 3 ≈ 0.462 to 1 2 .
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果