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

Miklavič, Štefko; Šparl, Primož

ENG

Prijava

Prva stran / Izpis gradiva

Izpis gradiva

A- | A+ | Natisni

Naslov:	Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups
Avtorji:	ID Miklavič, Štefko (Avtor) ID Šparl, Primož (Avtor)
Datoteke:	http://dx.doi.org/10.1002/jgt.20621
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	IAM - Inštitut Andrej Marušič
Opis:	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.
Ključne besede:	graph theory, Hamilton cycle, Hamilton path, n-HC-extendable, strongly n-HP-extendable, weakly n-HP-extendable, Cayley graph, abelian group
Leto izida:	2012
Št. strani:	str. 384-403
Številčenje:	Vol. 70, no. 4
PID:	20.500.12556/RUP-3539
ISSN:	0364-9024
UDK:	519.17
COBISS.SI-ID:	1024359764
Datum objave v RUP:	15.10.2013
Število ogledov:	2816
Število prenosov:	143
Metapodatki:
:	Kopiraj citat