Extremal Graph for Intersecting Odd Cycles

Xinmin Hou, Yu Qiu, Boyuan Liu

Abstract


An extremal graph for a graph $H$ on $n$ vertices is a graph on $n$ vertices with maximum number of edges that does not contain $H$ as a subgraph. Let $T_{n,r}$ be the Turán graph, which is the complete $r$-partite graph on $n$ vertices with part sizes that differ by at most one. The well-known Turán Theorem states that $T_{n,r}$ is the only extremal graph for complete graph $K_{r+1}$. Erdős et al. (1995) determined the extremal graphs for intersecting triangles and Chen et al. (2003) determined the maximum number of edges of the extremal graphs for intersecting cliques. In this paper, we determine the extremal graphs for intersecting odd cycles.

Keywords


Extremal graph; Intersecting odd cycles; Turán graph

Full Text:

PDF