Minimal hyper-Hamilton laceable graphs
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} \] {}.
- Hyper-Hamilton laceable and caterpillar-spannable product graphs
- Addendum to: ``Hamilton-laceable bi-powers of locally finite bipartite graphs
- Hamilton-laceable bi-powers of locally finite bipartite graphs
- Laceable knights
- scientific article; zbMATH DE number 4085690 (Why is no real title available?)
- Hamiltonian-laceability of star graphs
- Enumeration of Hamilton paths in ladders
- On edge extremal properties of Hamilton laceable bigraphs
This page was built for publication: Minimal hyper-Hamilton laceable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1310244)