On the 2-extendability of the generalized Petersen graphs. (English) Zbl 0723.05086

Summary: A graph G is n-extendable if it is connected, contains a set of n independent edges and every set of n independent edges extends to (i.e. is a subset of) a perfect matching. Combining the results of this and previous papers we answer the question of 2-extendability for all the generalized Petersen graphs G(n,k) with \(k\leq 7\) as well as for all G(n,k) with \(n\geq 3k+5\).


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI


[1] Coxeter, H.S.M., Self-dual configurations, and regular graphs, Bull. amer. math. soc., 56, 413-455, (1950) · Zbl 0040.22803
[2] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[3] Plummer, M.D., On n-extendable graphs, Discrete math., 31, 201-210, (1980) · Zbl 0442.05060
[4] G. Schrag, Automorphism groups and the full state spaces of the Petersen graph generalizations of G32, to appear in Discrete Mathematics. · Zbl 0644.05025
[5] G. Schrag and L. Cammack, Some full and fully deterministic generalized Petersen graphs, submitted. · Zbl 1097.05504
[6] Watkins, M., A theorem of Tait colorings with an application to the generalized Petersen graph, J. combin. theory, 6, 152-164, (1969) · Zbl 0175.50303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.