Classifying 2-extendable generalized Petersen graphs (Q1197056)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Classifying 2-extendable generalized Petersen graphs |
scientific article |
Statements
Classifying 2-extendable generalized Petersen graphs (English)
0 references
16 January 1993
0 references
A graph is \(n\)-extendable if it is connected, and if every set of \(n\) independent edges can be extended to a 1-factor. The generalized Petersen graph \(\text{GP}(n,k)\) consists of a cycle on vertices \(u_ 0,u_ 1,\dots,u_{n-1}\), \(n\) further vertices \(v_ 0,v_ 1,\dots,v_{n-1}\), and \(2n\) further edges of the form \(u_ iv_ i\) and \(v_ jv_ m\) where \(m=j+k\pmod n\). The author proves a conjecture of Cammack and Schrag to the effect that \(\text{GP}(n,k)\) is 2-extendable for all \(n\neq 2k\) or \(3k\) when \(k\geq 3\).
0 references
\(n\)-extendable graph
0 references
Petersen graph
0 references