Přejít k obsahu


Forbidden subgraphs and the hamiltonian index of a 2-connected graph

Citace:
HOLUB, P. Forbidden subgraphs and the hamiltonian index of a 2-connected graph. ARS COMBINATORIA, 2014, roč. 117, č. 1, s. 163-182. ISSN: 0381-7032
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Forbidden subgraphs and the hamiltonian index of a 2-connected graph
Rok vydání: 2014
Autoři: RNDr. Přemysl Holub Ph.D. ,
Abstrakt CZ: Hamiltonovský index grafu $G$ je nejmenší přirozené číslo $k$ takové, že $k$--tý iterovaný hranový graf $L^k(G)$ je hamiltonovský. Bedrossian charakterizoval všechny dvojice zakázaných indukovaných podgrafů, jež implikují hamiltonovskost ve $2$-souvislých grafech. V tomto článku jsou uvedeny některé horní meze pro hamiltonovský index $2$-souvislých grafů ve smyslu zakázaných, ne nutně indukovaných, podgrafů.
Abstrakt EN: Hamiltonian index of a graph $G$ is the smallest positive integer $k$, for which the $k$-th iterated line graph $L^k(G)$ is hamiltonian. Bedrossian characterized all pairs of forbidden induced subgraphs that imply hamiltonicity in $2$-connected graphs. In this paper, some upper bounds on the hamiltonian index of a $2$-connected graph in terms of forbidden not necessarily induced subgraphs are presented.
Klíčová slova

Zpět

Patička