On k-graceful, locally finite graphs (Q790132)

A finite graph G with e edges is k-graceful, if there is a one-to-one mapping \(h: V(G)\to \{0,1,...,k+e-1\}\) such that the edge differences \(| h(u)-h(v)|\) (for u\(v\in E(G))\) are all distinct and range from k to \(k+e-1\). Some bipartite graphs may be k-graceful for all k, but if a k-graceful finite graph G contains an odd cycle of length \(2j+1\), then \(k\leq j\) (e-j-1). This inequality, proved by the author in an earlier paper, is strengthened for the situation where G contains several edge- disjoint odd cycles. A countably infinite graph G (with both V(G) and E(G) infinite) is bijectively k-graceful if there is a bijection \(h: V(G)\to \{0,1,2,...\}\) such that the mapping taking u\(v\in E(G)\) to \(| h(u)-h(v)|\) is also a bijection of E(G) onto \(\{k,k+1,k+2,...\}\). The second result asserts that a locally finite graph is bijectively k-graceful for all \(k\geq 1\).