Revisiting the Hamiltonian theme in the square of a block: the Case of DT-graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F18%3A43950238" target="_blank" >RIV/49777513:23520/18:43950238 - isvavai.cz</a>

Výsledek na webu

<a href="http://intlpress.com/site/pub/pages/journals/items/joc/content/vols/0009/0001/a007/index.html" target="_blank" >http://intlpress.com/site/pub/pages/journals/items/joc/content/vols/0009/0001/a007/index.html</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4310/JOC.2018.v9.n1.a7" target="_blank" >10.4310/JOC.2018.v9.n1.a7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Revisiting the Hamiltonian theme in the square of a block: the Case of DT-graphs

Popis výsledku v původním jazyce

The square of a graph G, denoted G^2, is the graph obtained from G by joining by an edge any two nonadjacent vertices which have a common neighbor. A graph G is said to have F_k property if for any set of k distinct vertices {x_1,x_2,...,x_k} in G, there is a hamiltonian path from x_1 to x_2 in G^2 containig k-2 distinct edges of G of the form x_i z_i, i=3,...,k. In [7], it was proved that every 2-connected graph has the F_3 property. In the first part of this work, we extend this result by proving that every 2-connected DT-graph has the F_4 property (Theorem 2) and will show in the second part that this generalization holds for arbitrary 2-connected graphs, and that there exist 2-connected graphs which do not have the F_k property for any natural number k&gt;=5. Altogether, this answers the second problem raised in [4] in the affirmative.

Název v anglickém jazyce

Revisiting the Hamiltonian theme in the square of a block: the Case of DT-graphs

Popis výsledku anglicky

The square of a graph G, denoted G^2, is the graph obtained from G by joining by an edge any two nonadjacent vertices which have a common neighbor. A graph G is said to have F_k property if for any set of k distinct vertices {x_1,x_2,...,x_k} in G, there is a hamiltonian path from x_1 to x_2 in G^2 containig k-2 distinct edges of G of the form x_i z_i, i=3,...,k. In [7], it was proved that every 2-connected graph has the F_3 property. In the first part of this work, we extend this result by proving that every 2-connected DT-graph has the F_4 property (Theorem 2) and will show in the second part that this generalization holds for arbitrary 2-connected graphs, and that there exist 2-connected graphs which do not have the F_k property for any natural number k&gt;=5. Altogether, this answers the second problem raised in [4] in the affirmative.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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ů

Název periodika

Journal of Combinatorics

ISSN

2156-3527

e-ISSN

—

Svazek periodika

9

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

43

Strana od-do

119-161

Kód UT WoS článku

000422906100007

EID výsledku v databázi Scopus

—