A Note on Hamiltonian-intersecting families of graphs

Abstract

How many graphs on an n-point set can we find such that any two have connected intersection? Berger, Berkowitz, Devlin, Doppelt, Durham, Murthy and Vemuri showed that the maximum is exactly 1/2ⁿ⁻¹ of all graphs. Our aim in this short note is to give a ‘directed’ version of this result; we show that a family of oriented graphs such that any two have strongly-connected intersection has size at most 1/3ⁿ of all oriented graphs. We also show that a family of graphs such that any two have Hamiltonian intersection has size at most 1/2ⁿ of all graphs, verifying a conjecture of the above authors.