부산대학교 도서관

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.