Combinatorics and Optimization Seminar

Hamiltonian Properties of the 2-Block-Intersection Graphs of Twofold Triple Systems
Friday, 31 March 2017 - 2:30 pm to 3:00 pm
Room number: 
Registration required: 
Cost to attend: 
Free of charge
Event organizer: 
Event language: 

SPEAKER: Aras Erzurumluoglu

A <i> balanced incomplete block design </i> BIBD\((v,k,\lambda)\)
is a combinatorial design \((V,{\cal B})\) in which
(i) \(|V|=v\), (ii) \(|B|=k\) for each block \(B\) in \( {\cal B} \), and
(iii) each 2-subset of \(V \)occurs in precisely \(\lambda\) blocks of \({\cal B}\). A BIBD\((v,3,2)\) is called a <i> twofold triple system </i> and denoted TTS\((v)\). <br>

Given a combinatorial design \({\cal D}\) with block set \({\cal B}\),
the <i> \(i\)-block-intersection graph </i> (\(i\)-BIG) of \({\cal D}\) is the graph having \({\cal B}\) as its vertex set, and two vertices \(B_{1}\) and \(B_{2}\) adjacent if and only if \(|B_{1} \cap B_{2}| = i\). <br>

Recent joint work with David Pike settles the spectrum of TTSs
with connected non-hamiltonian 2-BIGs, as well as the spectrum of TTSs with
hamiltonian 2-BIGs (or equivalently, the spectrum of TTSs without and with
cyclic 2-intersecting Gray codes, respectively). In this talk I will present one or more of the techniques that we used to obtain these results.