izpis_h1_title_alt

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups
ID Miklavič, Štefko (Author), ID Šparl, Primož (Author)

URLURL - Presentation file, Visit http://dx.doi.org/10.1002/jgt.20621 This link opens in a new window

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.

Language:English
Keywords:graph theory, Hamilton cycle, Hamilton path, n-HC-extendable, strongly n-HP-extendable, weakly n-HP-extendable, Cayley graph, abelian group
Work type:Not categorized
Typology:1.01 - Original Scientific Article
Organization:PEF - Faculty of Education
Year:2012
Number of pages:Str. 384-403
Numbering:Vol. 70, no. 4
PID:20.500.12556/RUL-84783 This link opens in a new window
UDC:519.17
ISSN on article:0364-9024
DOI:10.1002/jgt.20621 This link opens in a new window
COBISS.SI-ID:1024359764 This link opens in a new window
Publication date in RUL:09.09.2016
Views:1772
Downloads:254
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Record is a part of a journal

Title:Journal of graph theory
Shortened title:J. graph theory
Publisher:J. Wiley & Sons
ISSN:0364-9024
COBISS.SI-ID:25747712 This link opens in a new window

Secondary language

Language:Slovenian
Keywords:teorija grafov, Hamiltonov cikel, Hamiltonova pot, Cayleyjev graf, Abelova grupa

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back