Logo BSU

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/6970
Title: Hamiltonian properties of triangular grid graphs
Authors: Orlovich, Yu. L.
Werner, Frank
Gordon, Valery S.
Keywords: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Issue Date: 2007
Citation: Orlovich, Yury L. Hamiltonian properties of triangular grid graphs / Y.Orlovich, F.Werner, V.Gordon // Discrete Mathematics. - 2008. - №308. - P. 6166–6188.
Abstract: A triangular grid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional triangular grid. In 2000, Reay and Zamfirescu showed that all 2-connected, linearly-convex triangular grid graphs (with the exception of one of them) are hamiltonian. The only exception is a graph D which is the linearly-convex hull of the Star of David. We extend this result to a wider class of locally connected triangular grid graphs. Namely, we prove that all connected, locally connected triangular grid graphs (with the same exception of graph D) are hamiltonian. Moreover, we present a sufficient condition for a connected graph to be fully cycle extendable. We also show that the problem HAMILTONIAN CYCLE is NP-complete for triangular grid graphs.
Description: Available online at www.sciencedirect.com
URI: http://elib.bsu.by/handle/123456789/6970
Appears in Collections:Статьи факультета прикладной математики и информатики

Files in This Item:
File Description SizeFormat 
F54B581.pdf2,93 MBAdobe PDFView/Open


PlumX

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.