No label defined (Q3815329)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4085690
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4085690 |
Statements
1987
0 references
bipartite graph
0 references
Hamilton laceable
0 references
equitable Hamilton laceable graph
0 references
permutation graph
0 references
0.87392258644104
0 references
0.8171080946922302
0 references
0.8018542528152466
0 references
0.8008638024330139
0 references
[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?
0 references