آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 112 |
| تعداد مقالات | 1,271 |
| تعداد مشاهده مقاله | 1,239,020 |
| تعداد دریافت فایل اصل مقاله | 1,098,418 |
Graceful labelings of the generalized Petersen graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 6، دوره 2، شماره 2، آذر 2017، صفحه 149-159 اصل مقاله (451.24 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2017.25918.1055 | ||
| نویسندگان | ||
| Aleksander Vesel* 1؛ Zehui Shao2؛ Fei Deng3؛ Zepeng Li4 | ||
| 1University of Maribor | ||
| 2School of Information Science & Technology, Chengdu University, Chengdu, China | ||
| 3College of Information Science and Technology, Chengdu University of Technology, Chengdu, China | ||
| 4Key Laboratory of High Confidence Software Technologies, Peking University, Peking, China | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| graceful labeling؛ generalized Petersen graph؛ heuristic | ||
| مراجع | ||
|
[1] G.S. Bloom and S.W. Golomb, Applications of numbered undirected graphs, Proceedings of the IEEE 65 (1977), no. 4, 562–570.
[2] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 16 (2009), no. 6, 1–219.
[3] T.A. Redl, Graceful graphs and graceful labelings: two mathematical programming formulations and some other new results, Congr. Numer. 164 (2003), 17–32.
[4] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, 1966, pp. 349–355.
[5] A. Steimle and W. Staton, The isomorphism classes of the generalized petersen graphs, Discrete Math. 309 (2009), no. 1, 231–237. | ||
|
آمار تعداد مشاهده مقاله: 1,550 تعداد دریافت فایل اصل مقاله: 1,261 |
||