Minimal hyper-Hamilton laceable graphs (Q1310244)

A bipartite graph is equitable if both colour classes (the parts of the vertex bipartition) have the same cardinality. It is nearly equitable if the larger colour class has one more vertex than the smaller. Since a bipartite graph is not hamilton-connected, the notion is generalised as follows: A bipartite graph is hamilton laceable if either it is equitable and for each pair of vertices \(x,y\) of opposite colours there is an \(x\)- \(y\) hamilton path or it is nearly equitable and if for each pair of vertices \(x,y\) of the larger class there is an \(x\)-\(y\) hamilton path. The authors further generalise this concept and define a bipartite graph \(G\) to be hyper-hamilton laceable if either \(G\) is equitable and for every vertex \(v\), \(G-v\) is hamilton laceable or \(G\) is nearly equitable and for any \(v\) in the larger colour class \(G-v\) is hamilton laceable. After investigating this property for product graphs, the authors prove that if \(m\) is the minimum number of edges in a hyper-hamilton laceable graph on \(n\) vertices, then \[ m=3k \text{ if } n=2k\;(k>2) \tag{i} \] \[ 3k \leq m \leq 4k-1 \text{ if } n=2k+1\;(k>1). \tag{ii} \] {}.