Edge-Maximal C2k+1-vertex disjoint Free Graphs

Abstract

Let k ≥1 be a positive integer and G (n;V_2k+1) the class of graphs on n vertices containing no 2k+1 vertex disjoint cycles. Let f (n;V_2k+1) = max{ ε(G) : G ∈ G(n;V_2k+1)}. In this paper we determine f (n;V_2k+1) and characterise the edge maximal members in G (n;V_2k+1) for k = 1 and 2.

Keywords: Extremal graph; Cycle; Vertex disjoint.

2000 Mathematics Subject Classification. Primary 05C38 ; secondary 05C35