TY - JOUR
ID - 13646
TI - Graceful labelings of the generalized Petersen graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Vesel, Aleksander
AU - Shao, Zehui
AU - Deng, Fei
AU - Li, Zepeng
AD - University of Maribor
AD - School of Information Science & Technology, Chengdu University, Chengdu, China
AD - College of Information Science and Technology, Chengdu University of Technology, Chengdu, China
AD - Key Laboratory of High Confidence Software Technologies, Peking University, Peking, China
Y1 - 2017
PY - 2017
VL - 2
IS - 2
SP - 149
EP - 159
KW - graceful labeling
KW - generalized Petersen graph
KW - heuristic
DO - 10.22049/cco.2017.25918.1055
N2 - 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, ldots, u_n} cup {v_1, v_2, ldots, 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.
UR - http://comb-opt.azaruniv.ac.ir/article_13646.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13646_07d33d001066dc9b0e695120e6125c8a.pdf
ER -