Two Hamilton cycles in bipartite reflective Kneser graphs
type: Item
instance of: scholarly article
title: Two Hamilton cycles in bipartite reflective Kneser graphs
zbMATH Open document ID: 0659.05063
DOI: 10.1016/0012-365X(88)90194-X
author: S. H. Smith
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: For integers i, j with \(0<i<j\), let \(RG_{ij}\) be the bipartite graph the vertex-classes \(V_ 1\) and \(V_ 2\) of which are the \((i+j)\)-tuples over \(\{\) 0,1\(\}\) of Hamming weight i and j, respectively, and \((a_ 1,...,a_{i+j})\in V_ 1\), \((b_ 1,...,b_{i+j})\in V_ 2\) are adjacent iff \(a_ k=1\) implies \(b_ k=1\), \(k=1,...,i+j\). According to a conjecture due to \textit{I. Havel} [Graphs and other combinatorial topics, Proc. 3rd Czech. Symp., Prague 1982, Teubner-Texte Math. 59, 101-108 (1983; Zbl 0528.05030)] concerning such graphs \(RG_{ij}\) the authors verify the graphs \(RG_{9,10}\) and \(RG_{7,9}\) to be Hamiltonian. The Hamilton cycles are constructed by considering group actions on graphs and their quotient graphs.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 4077269
zbMATH Keywords: Hamilton cycles
reviewed by: Günter Schaar
MaRDI profile type: Publication
cites work: Q3691702
cites work: Q3762351
full work available at URL: 0012-365x(88)90194-x
OpenAlex ID: W1988175779
description: scientific article; zbMATH DE number 4077269