𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On constructing snakes in powers of complete graphs

✍ Scribed by Jerzy Wojciechowski

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
737 KB
Volume
181
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We prove the conjecture of Abbott and Katchalski that for every m ~> 2 there is a positive constant 2,. such that S(K~n ) >~ 2mnd-lS(Ka~ -1) where S(Ka~) is the length of the longest snake (cycle without chords) in the cartesian product K~ of d copies of the complete graph Kin. As a corollary, we conclude that for any finite set P of primes there is a constant c = c(P) > 0 such that S(Ka,)>~cn d-l for any n divisible by an element of P and any d~> 1.

πŸ“œ SIMILAR VOLUMES

Further results on snakes in powers of c
Further results on snakes in powers of complete graphs
✍ H.L. Abbott; M. Katchalski πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 553 KB

Abbott, H.L. and M. Katchalski, Further results on snakes in powers of complete graphs, Discrete Mathematics 91 (1991) 111-120. By a snake in a finite graph G is meant a cycle without chords. Denoted by S(G) the length of a longest snake in G. In this paper we obtain a new lower bound for S(G) in t

A result on extendibility in the powers
A result on extendibility in the powers of graphs
✍ Kara Walcher Shavo πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 309 KB

## Abstract Let __G__ be a graph on __p__ vertices. Then for a positive integer __n__, __G__ is said to be __n__‐extendible if (i) __n__ < __p__/2, (ii) __G__ has a set of __n__ independent edges, and (iii) every such set is contained in a perfect matching of __G__. The purpose of this article is t