A best possible result for the square of a 2-block to be hamiltonian

被引：1

作者：

Ekstein, Jan ^{[1
,2
]}

Fleischner, Herbert ^{[3
]}

机构：

[1] Univ West Bohemia, Fac Appl Sci, Dept Math, Tech 8, Plzen 30614, Czech Republic

[2] Univ West Bohemia, Fac Appl Sci, European Ctr Excellence NTIS New Technol Informat, Tech 8, Plzen 30614, Czech Republic

[3] Vienna Univ Technol, Inst Log & Computat, Algorithms & Complex Grp, Favoritenstr 9-11, A-1040 Vienna, EU, Austria

来源：

DISCRETE MATHEMATICS | 2021年 / 344卷 / 01期

基金：

奥地利科学基金会;

关键词：

Square of graphs; Hamiltonian cycles; SHORT PROOF; BLOCK; THEME;

D O I：

10.1016/j.disc.2020.112158

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is shown that for any choice of four different vertices x(1), ..., x(4) in a 2-block G of order p > 3, there is a hamiltonian cycle in G(2) containing four different edges x(i)y(i) of E(G) for certain vertices y(i), i = 1, 2, 3, 4. This result is best possible. (C) 2020 Elsevier B.V. All rights reserved.

引用

页数：6

共 11 条

[1]

Alstrup S, 2018, SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1645

[2]

Bondy J.A., 2008, GTM 244

[3] Revisiting the Hamiltonian theme in the square of a block: the case of DT-graphs [J].