Lupa

Show document

A- | A+ | Print
Title:Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups
Authors:Miklavič, Štefko (Author)
Šparl, Primož (Author)
Files:URL http://dx.doi.org/10.1002/jgt.20621
 
Language:English
Work type:Not categorized
Tipology:1.01 - Original Scientific Article
Organization:IAM - Andrej Marušič Institute
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:graph theory, Hamilton cycle, Hamilton path, n-HC-extendable, strongly n-HP-extendable, weakly n-HP-extendable, Cayley graph, abelian group
Year of publishing:2012
Number of pages:str. 384-403
Numbering:Vol. 70, no. 4
ISSN:0364-9024
UDC:519.17
COBISS_ID:1024359764 Link is opened in a new window
Views:1296
Downloads:79
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:Document is not linked to any category.
:
  
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
Share:Bookmark and Share

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

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

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica