Hamiltonovske problémy v dědičných třidách grafů charakterizované zakázanými indukovanými podgrafy.

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F09%3A00501757" target="_blank" >RIV/49777513:23520/09:00501757 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Hamiltonovske problémy v dědičných třidách grafů charakterizované zakázanými indukovanými podgrafy.

Popis výsledku v původním jazyce

Luczak and Pfender cite{88} proved that if a graph $G$ is 3-connected and $K_{1,3}P_{11}$-free, then $G$ is hamiltonian. Moreover, Luczak et al. cite{8} showed an example a non hamiltonian 3-connected $CP_{12}$-free graph. This result give a motivationto find an upper bound for the number $i$ such that every 3-connected $CZ_{i}$-free graph is hamiltonian. We will show that if a $G$ is 3-connected and $CZ_{6}$-free graph, then $G$ is hamiltonian. Pairs of connected graphs $X,Y$ such that a graph $G$ being 2-connected and $XY$-free implies $G$ is hamiltonian were characterized by Bedrossian. Using the closure concept for claw-free graphs, Ryj' av cek simplified the characterization by showing that if considering the closure of $G$, the list in the Bedrossian's characterization can be reduced to one pair, namely, $K_{1,3},N_{1,1,1}$ (where $K_{i,j}$ is the complete bipartite graph, and $N_{i,j,k}$ is the graph obtained by identifying end vertices of three disjoint paths of l

Název v anglickém jazyce

Hamiltonovske problémy v dědičných třidách grafů charakterizované zakázanými indukovanými podgrafy.

Popis výsledku anglicky

Luczak and Pfender cite{88} proved that if a graph $G$ is 3-connected and $K_{1,3}P_{11}$-free, then $G$ is hamiltonian. Moreover, Luczak et al. cite{8} showed an example a non hamiltonian 3-connected $CP_{12}$-free graph. This result give a motivationto find an upper bound for the number $i$ such that every 3-connected $CZ_{i}$-free graph is hamiltonian. We will show that if a $G$ is 3-connected and $CZ_{6}$-free graph, then $G$ is hamiltonian. Pairs of connected graphs $X,Y$ such that a graph $G$ being 2-connected and $XY$-free implies $G$ is hamiltonian were characterized by Bedrossian. Using the closure concept for claw-free graphs, Ryj' av cek simplified the characterization by showing that if considering the closure of $G$, the list in the Bedrossian's characterization can be reduced to one pair, namely, $K_{1,3},N_{1,1,1}$ (where $K_{i,j}$ is the complete bipartite graph, and $N_{i,j,k}$ is the graph obtained by identifying end vertices of three disjoint paths of l

Druh

O - Ostatní výsledky

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2009

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů