Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs (Q2630707)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs |
scientific article |
Statements
Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs (English)
0 references
21 July 2016
0 references
It is proved that the block graph of a \(\mathrm{BIBD}(v,k,1)\) design, where two blocks are adjacent if they are disjoint, is Hamiltonian. A polynomial-time algorithm is described for finding cycles in the block graph of a \(\mathrm{BIBD}(v,k,\lambda)\) with \(v > 5k^2 +1\) if \(\lambda > 1\), and \(v > (2+\sqrt{3})k^2 +1\) if \(\lambda =1\).
0 references
block design
0 references
block graph
0 references
Hamilton cycle
0 references