✦ LIBER ✦

On the 2-extendability of the generalized Petersen graphs

✍ Scribed by Gerald Schrag; Larry Cammack

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 731 KB
Volume: 78
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90174-x

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is n-extendable if it is connected, contains a set of rr 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 s 7 as well as for all G(n, k) with n a 3k + 5.

📜 SIMILAR VOLUMES

Classifying 2-extendable generalized Pet

Classifying 2-extendable generalized Petersen graphs

✍ Qinglin Yu 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 559 KB

A graph is said to be 2-extendable if any two edges which do not have a common vertex are contained in a l-factor of the graph. In this paper, we show that the generalized Petersen graph GP(n, k) is 2-extandable for all n # 2k or 3k whenever k 2 3, as conjectured by Cammack and Schrag.

On the crossing numbers of certain gener

On the crossing numbers of certain generalized Petersen graphs

✍ Dan McQuillan; R. Bruce Richter 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 484 KB

In his paper on the crossing numbers of generalized Petersen graphs, Fiorini proves that P(8, 3) has crossing number 4 and claims at the end that P(10, 3) also has crossing number 4. In this article, we give a short proof of the first claim and show that the second claim is false. The techniques are

A Note on the Generalized Petersen Graph

A Note on the Generalized Petersen Graphs That Are Also Cayley Graphs

✍ Marko Lovrečič Saražin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 483 KB

The aim of this note is to present a short proof of a result of Nedela and S8 koviera (J. Graph Theory 19 (1995, 1 11)) concerning those generalized Petersen graphs that are also Cayley graphs. In that paper the authors chose the heavy weaponry of regular maps on closed connected orientable surfaces

The 2-extendability of strongly regular

The 2-extendability of strongly regular graphs

✍ Dingjun Lou; Qingwei Zhu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 362 KB

On the Extendability of Linear Codes

✍ Tatsuya Maruta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 237 KB

Symposium on Inform. Theory, Whistler, Canada,'' pp. 345) proved that every [n, k, d] O code with gcd(d, q)"1 and with all weights congruent to 0 or d (modulo q) is extendable to an O code with all weights congruent to 0 or d#1 (modulo q). We give another elementary geometrical proof of this theor

On the Chromatic Roots of Generalized Th

On the Chromatic Roots of Generalized Theta Graphs

✍ Jason I. Brown; Carl Hickman; Alan D. Sokal; David G. Wagner 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 242 KB

The generalized theta graph G s1, ..., sk consists of a pair of endvertices joined by k internally disjoint paths of lengths s 1 , ..., s k \ 1. We prove that the roots of the chromatic polynomial p(G s1, ..., sk , z) of a k-ary generalized theta graph all lie in the disc |z -1| [ [1+o(1)] k/log k,