scientific article; zbMATH DE number 4085690

From MaRDI portal
Publication:3815329





[For the entire collection see Zbl 0638.00009.] Let G be a bipartite graph with vertex partition \(V=X\cup Y\). If \(| X| =| Y|\), G is said to be equitable. If further, for every x in X and y in Y there is an x-y Hamilton path in G, it is said to be Hamilton laceable. If \(| X| =| Y| +1.\) G is said to be nearly equitable. If further, for every u, v in X there is a u-v Hamilton path in G, then G is said to be Hamilton laceable. The following results are proved: (1) If G is equitable Hamilton laceable, then so is \(G\times K_ 2\), where \(\times\) denotes the Cartesian product. (Corollary: \(Q_ n\) is Hamilton laceable). (2) Let G be equitable Hamilton laceable. Add u to X and all edges uy, \(y\in Y\). Add v to Y and all edges vx, \(x\in X\). The resulting graph J(G) is Hamilton laceable. The following open problem is posed: If G is an equitable Hamilton laceable graph, under what conditions is the permutation graph \(P_{\alpha}(G)\) Hamilton laceable?











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815329)