ON THE t-EXTENDABILITY OF THE GENERALIZED PETERSEN GRAPHS

Gerald Schrag and Larry Cammack Central Missouri State University

Introduction. In an earlier paper (see [5]) we investigated the existence of full sets of states and full sets of dispersion free states on the orthomodular lattices and posets arising from the dualization of the generalized Petersen graphs. In particular, investigation of those orthomodular structures admitting full sets of dispersion free states led in a natural way to the question of 2-extendability (as defined by Plummer [4]) of the generalized Petersen graphs and was partially answered in [6] and [7].

In this paper we answer completely the question of textendability (also defined by Plummer [4]) on the generalized Petersen graphs where t is not equal to 2.

Terminology. All graphs in this paper are in the sense of Harary [2]. Recall that a \underline{perfect matching} of a graph G is a set of independent (i.e., non-adjacent) edges which together cover all the points of G.

Following M. D. Plummer [4], we define a graph G to be \underline{t − extendable} if it is connected, contains a set of t independent edges and every set of t independent edges extends to (i.e. is a subset of) a perfect matching.

Following Watkins [8] and Coxeter [1] we define the \underline{generalized} \underline{P etersen graphs} G(n, k) as follows. The points are u_{0}, u_{1}, …, u_{n−1}, v_{0}, v_{1}, …, v_{n−1} and the edges are [u_{i}, u_{i+1}] (called \underline{outer edges}), [v_{i}, v_{i+k}] (called \underline{inner edges}), and [u_{i}, v_{i}] (called \underline{spokes}) where all subscripts are modulo n and 1 < 2k < n . These edges will be denoted by a_{i}, b_{i}, and c_{i} respectively. Note that the Petersen graph is G(5, 2) . Each connected component of the subgraph generated by v_{0}, v_{1}, …, v_{n−1} is called an \underline{inner rim}.

Main Results.

\underline{T heorem 1}. The generalized Petersen graphs G(n, k) are 1extendable and n-extendable.

\underline{P roof}. For i = 0, 1, 2, …, n − 1 define perfect matchings M_{i} by the set { a_{i}, a_{i+2}, …, a_{i+2k−2}, b_{i}, b_{i+1}, …, b_{i+k−1}, c_{i+2k}, c_{i+2k+1}, …, c_{i+n−1}}. Since this set contains at least one outer edge, at least one inner edge, and at least one spoke, a given edge is covered by at least one of these perfect matchings. Thus every G(n, k) is 1-extendable.

The first part of this theorem also follows from a result of Little, et al [3]. However, a proof using this approach depends on a characterization of d-covered graphs which is not needed here.

Since every generalized Petersen graph has a perfect matching, G(n, k) is n-extendable for all n and k .

It is worth noting here that because of Plummer’s Theorem (Theorem 2.2 of [4]), all G(n, k) which are 2-extendable are also 1extendable. However, the question of 2-extendability has not been completely answered for all G(n, k) and in fact it is known that some of G(n, k) are not 2-extendable (see Schrag and Cammack [7]). For example, the edges a_{2} and c_{0} do not extend to a perfect matching in G(5, 2) , the original Petersen graph. (see Figure 1.)

\underline{T heorem 2}. If t > 2 , then G(n, k) is t-extendable if and only if t = n.

\underline{P roof}. No set of independent edges to which a_{1}, a_{n−2}, and b_{0} extend can cover u_{0} . Furthermore these three edges are independent unless u_{n−2} = u_{2} in which case n = 4 , or a_{n−2} = a_{1} in which case n = 3 (a_{i} and b_{j} are always independent for any i and j). Thus G(n, k) is not 3-extendable if n > 4. By Plummer’s Theorem G(n, k) not ( t-1)-extendable implies G(n, k) not t-extendable for t < n . Thus no G(n, k) is t-extendable for 2 < t < n . Note that the fact that G(n, k) is n-extendable but not ( n-1)-extendable does not contradict Plummer’s theorem since the hypothesis is not satisfied if t = n .

Now note that n = 4 implies that G(n, k) = G(4, 1) and n = 3 implies that G(n, k) = G(3, 1) . That G(3, 1) is 3-extendable and that G(4, 1) is 4-extendable are restatements of Theorem 1 with n = 3 and n = 4 . G(4, 1) is not 3-extendable since a_{1}, b_{0}, and c_{3} do not extend to a perfect matching.

For the reader’s convenience we conclude with a summary of the known results on t-extendability of the generalized Petersen graphs.

1. G(n, k) is 1-extendable for all n and k .

2. G(3k, k) is not 2-extendable for any k .

3. G(n, 1) is 2-extendable if and only if n is even.

4. G(n, 2) is 2-extendable if and only if n ≠ 5, 6, or 8 .

5. If 3 ≤ k ≤ 7 , G(n, k) is 2-extendable if and only if n ≠ 3k .

6. If k ≥ 4, then any pair of independent edges of G(n, k) at least one of which is a spoke can be extended to a perfect matching.

7. G(n, k) is 2-extendable for all n and k such that n ≥ 3k + 5 and k ≥ 2 .

8. If t > 2 , then G(n, k) is t-extendable if and only if t = n.

9. G(n, k) is n-extendable for all n and k .

It is worth noting that if the conditions of the definition of

G(n, k) are relaxed so as to allow n = 2k, then it is easy to show

that G(2k, k) is t-extendable if and only if t = 1 or t = 2k .

The only question remaining is that of 2-extendability of

G(n, k) for k > 7 and n < 3k + 5 where n ≠ 3k . It is

conjectured that these are all 2-extendable.

\underline{References}

1. H. S. M. Coxeter, “Self-Dual Configurations and Regular Graphs,” Bulletin of the American Mathematical Society, 56(1950) 413–455.

2. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

3. H. C. Little, D. Grant and D. A. Holton, “On Defect d-Matchings in Graphs,” Discrete Mathematics, 13(1975) 41–54.

4. M. D. Plummer, “On n-Extendable Graphs,” Discrete Mathematics, 31(1980) 201–210.

5. G. Schrag, “Automorphism Groups and the Full State Spaces of the Petersen Graphs Generalizations of G_{32} ,” Discrete Mathematics, 70(1988) 185–198.

6. G. Schrag and L. Cammack, “Some Full and Fully Deterministic Generalized Petersen Graphs,” CMSU preprint.

7. G. Schrag and L. Cammack, “On the 2-Extendability of the Generalized Petersen Graphs,” to appear in Discrete Mathematics.

8. M. Watkins, “A Theorem on Tait Colorings with an Application to the Generalized Petersen Graph,” Journal of Combinatorial Theory, 6(1959) 152–164.