Vesel, A., Shao, Z., Deng, F., Li, Z. (2017). Graceful labelings of the generalized Petersen graphs. Communications in Combinatorics and Optimization, 2(2), 149-159. doi: 10.22049/cco.2017.25918.1055

Aleksander Vesel; Zehui Shao; Fei Deng; Zepeng Li. "Graceful labelings of the generalized Petersen graphs". Communications in Combinatorics and Optimization, 2, 2, 2017, 149-159. doi: 10.22049/cco.2017.25918.1055

Vesel, A., Shao, Z., Deng, F., Li, Z. (2017). 'Graceful labelings of the generalized Petersen graphs', Communications in Combinatorics and Optimization, 2(2), pp. 149-159. doi: 10.22049/cco.2017.25918.1055

Vesel, A., Shao, Z., Deng, F., Li, Z. Graceful labelings of the generalized Petersen graphs. Communications in Combinatorics and Optimization, 2017; 2(2): 149-159. doi: 10.22049/cco.2017.25918.1055

Graceful labelings of the generalized Petersen graphs

^{2}School of Information Science & Technology, Chengdu University, Chengdu, China

^{3}College of Information Science and Technology, Chengdu University of Technology, Chengdu, China

^{4}Key Laboratory of High Confidence Software Technologies, Peking University, Peking, China

Abstract

A graceful labeling of a graph $G=(V,E)$ with $m$ edges is an injection $f: V(G) rightarrow {0,1,ldots,m}$ such that the resulting edge labels obtained by $|f(u)-f(v)|$ on every edge $uv$ are pairwise distinct. For natural numbers $n$ and $k$, where $n > 2k$, a generalized Petersen graph $P(n, k)$ is the graph whose vertex set is ${u_1, u_2, cdots, u_n} cup {v_1, v_2, cdots, v_n}$ and its edge set is ${u_iu_{i+1}, u_iv_i, v_iv_{i+k} : 1 leq i leq n }$, where subscript arithmetic is done modulo $n$. We propose a backtracking algorithm with a specific static variable ordering and dynamic value ordering to find graceful labelings for generalized Petersen graphs. Experimental results show that the presented approach strongly outperforms the standard backtracking algorithm. The proposed algorithm is able to find graceful labelings for all generalized Petersen graphs $P(n, k)$ with $n le 75$ within only several seconds.