Premium
Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups
Author(s) -
MiklaviČ Štefko,
Šparl Primož
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20621
Subject(s) - cayley graph , mathematics , combinatorics , abelian group , hamiltonian path , path (computing) , induced path , discrete mathematics , graph , shortest path problem , longest path problem , computer science , programming language
In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is n ‐ HC‐extendable if it contains a path of length n and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ 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 Γ. Moreover, Γ 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 Γ 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. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory