Step 1 And K Cyclic Graph Induced Matching Scalability

Graphs considered in this paper are finite and simple. For a graph G, its vertex set and edge set are denoted by V(G) and E(G) respectively. For any vertex v e V(G), the neighbor set N(v) of v is defined byN{v) = {u∈ V(G) \ {v} | uv ∈E(G)} For M (?) E(G), setV(M) = {u∈ V(G)| there is a vertex v ∈ V(G) such that uv ∈ M)For S(?)V(G), setE(S) = {uv ∈ E{G) |u,v∈S}.A set M (?) E(G) of edges is called a matching of G if no two of them share a common endpoint. A matching is perfect if it covers all vertices of G. A matching M is induced if E(V(M)) = M. We say that a graph G is induced matching extendable, shortly IM-extendable, if every induced matching M of G is included in a perfect matching of G.The IM-extendability problem has attracted many graph theorists due to its strongly theoretical interest. Some researches on IM-extendable graphs can be found in [14, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36].We will denote by C2n(1, k) the cyclic graph with 2n vertices x0,x1, ... ,x2n-1, such that xixj is an edge of C2n(1, k) if either i - j = ±1 (mod 2n) or i - j = ±k (mod 2n). About the extendability of cyclic graphs the following results have been known.Lemma A C2n(1, 2) is not IM-extendable for n≥5.Lemma B C2n(1,n) is IM-extendable for n≥2.Lemma C C2n(1, 3) is IM-extendable for n ≥ 4.Lemma D C2n(1,n - 1) is IM-extendable for n≥3.In this paper we investigate the IM-extendability of cyclic graphs. The following results are established.Lemma 1 C2n(1, 4) is extendable if and only if either 3≤n≤8 or n = 10,11. Lemma 2 C2n(1, 2/3n) is IM-extendable if and only if n ≤ 6.Lemma 3 C2n(1, 2/5n) is not IM-extendable for n ≥ 25 and n = 5. It is IM-extendable for n = 10.Lemma 4 C2n(1, 4/5n) is not IM-extendable for n ≥ 20. It is IM-extendable for n = 5 and n = 10.Lemma 5 C2n(1,n/2) is IM-extendable for n ≥ 4.Lemma 6 C2n(1, 2n+2/3) is IM-extendable if and only if n ≤ 14.Lemma 7 C2n(1, 2n-2/3) is not IM-extendable for n ≥ 19 and is IM-extendable for n≤ 13.Lemma 8 C2n(1, 2n+1/3) is IM-extendable for n ≥ 4. Lemma 9 C2n(1,2n-1/3) is IM-extendable for n≥5.　 Lemma 10 C2n(1,k) is not IM-extendable, wherek≠2,,3,4, n- 1, n, 2/3n, 2/5n, 4/5n,n2/,2n-2/3,2n+2/3,2n-1,2n+1/3.Theorem Except for C30(1,6), C40(1,8), C30(1,12), and C32(1,10), the only IM-extendable graphs in C2n(1,k) are C2n(1,3) for n≥4; C2n(1,n - 1) for n≥3; C2n(1,n) for n≥2; C2n(1, n/2) for n≥4; C2n(1, 2n-1/3) for n≥5; C2n(1,2n+1/3) for n≥4; C2b(1,4) for 3 ≤ n≤ 8 or n = 10,11; C2n(1, 2n+2/3) for n ≤ 14; C2n(1, 2n-2/3) for n ≤ 13; C4(1, 2); C6(1,2);C8(1,2);andC20(1,8).