Povzetek

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

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL PEF - Pedagoška fakulteta
UDK: 519.17
COBISS: 1024359764 Povezava se bo odprla v novem oknu
ISSN: 0364-9024
Št. ogledov: 1113
Št. prenosov: 239
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarne ključne besede: teorija grafov;Hamiltonov cikel;Hamiltonova pot;Cayleyjev graf;Abelova grupa;
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 384-403
Letnik: ǂVol. ǂ70
Zvezek: ǂno. ǂ4
Čas izdaje: 2012
DOI: 10.1002/jgt.20621
ID: 1477168
Priporočena dela:
, delo diplomskega seminarja