Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

Štefko Miklavič (Author), Primož Šparl (Author)

Abstract

In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph ▫$\Gamma$▫ is ▫$n$▫-HC-extendable if it contains a path of length ▫$n$▫ and if every such path is contained in some Hamilton cycle of ▫$\Gamma$▫. Similarly, ▫$\Gamma$▫ is weakly ▫$n$▫-HP-extendable if it contains a path of length ▫$n$▫ and if every such path is contained in some Hamilton path of ▫$\Gamma$▫. Moreover, ▫$\Gamma$▫ is strongly ▫$n$▫-HP-extendable if it contains a path of length ▫$n$▫ and if for every such path $P$ there is a Hamilton path of ▫$\Gamma$▫ starting with ▫$P$▫. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2-HC-extendable and a complete classification of 3-HC-extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4-HP-extendable.

Keywords

teorija grafov;Hamiltonov cikel;Hamiltonova pot;Cayleyjev graf;Abelova grupa;graph theory;Hamilton cycle;Hamilton path;n-HC-extendable;strongly n-HP-extendable;weakly n-HP-extendable;Cayley graph;abelian group;

Data

Language:	English
Year of publishing:	2012
Typology:	1.01 - Original Scientific Article
Organization:	UL PEF - Faculty of Education
UDC:	519.17
COBISS:	1024359764
ISSN:	0364-9024
Views:	1113
Downloads:	239
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary keywords:	teorija grafov;Hamiltonov cikel;Hamiltonova pot;Cayleyjev graf;Abelova grupa;
Type (COBISS):	Not categorized
Pages:	str. 384-403
Volume:	ǂVol. ǂ70
Issue:	ǂno. ǂ4
Chronology:	2012
DOI:	10.1002/jgt.20621
ID:	1477168