Let $ f $ be a set-ordered edge-magic labeling of a graph $ G $ from $ V(G) $ and $ E(G) $ to $ [0, p-1] $ and $ [1, p-1] $, respectively; it also satisfies the following conditions: $ |f(V(G))| = p $, $ \max f(X) < \min f(Y) $, and $ f(x)+f(y)+f(xy) = C $ for each edge $ xy\in E(G) $. In this paper, we removed the restriction that the labeling of vertices could not be repeated, and presented the concept of magical colorings including edge-magic coloring, edge-difference coloring, felicitous-difference coloring, and graceful-difference coloring. We studied the magical colorings on the tree and proved the existence of four kinds of magical colorings on the tree from a set-ordered edge-magic labeling. Further, we revealed the transformation relationship between these kinds of colorings.
Citation: Jing Su, Qiyue Zhang, Bing Yao. The connection between the magical coloring of trees[J]. AIMS Mathematics, 2024, 9(10): 27896-27907. doi: 10.3934/math.20241354
Let $ f $ be a set-ordered edge-magic labeling of a graph $ G $ from $ V(G) $ and $ E(G) $ to $ [0, p-1] $ and $ [1, p-1] $, respectively; it also satisfies the following conditions: $ |f(V(G))| = p $, $ \max f(X) < \min f(Y) $, and $ f(x)+f(y)+f(xy) = C $ for each edge $ xy\in E(G) $. In this paper, we removed the restriction that the labeling of vertices could not be repeated, and presented the concept of magical colorings including edge-magic coloring, edge-difference coloring, felicitous-difference coloring, and graceful-difference coloring. We studied the magical colorings on the tree and proved the existence of four kinds of magical colorings on the tree from a set-ordered edge-magic labeling. Further, we revealed the transformation relationship between these kinds of colorings.
[1] | A. Gheorghiu, T. Kapourniotis, E. Kashefi, Verification of quantum computation: An over view of existing approaches, Theory Math. Syst., 63 (2019), 715–808. https://doi.org/10.1007/s00224-018-9872-3 doi: 10.1007/s00224-018-9872-3 |
[2] | S. Suhail, R. Hussain, A. Khan, C. S. Hong, On the role of hash-based signatures in quantum-safe internet of things: Current solutions and future directions, IEEE Internet Things, 8 (2021), 1–17. https://doi.org/10.1109/JIOT.2020.3013019 doi: 10.1109/JIOT.2020.3013019 |
[3] | S. Katsumata, T. Matsuda, A. Takayasu, Lattice-based revocable (hierarchical) IBE with decryption key exposure resistance, Theor. Comput. Sci., 809 (2020), 103–136. https://doi.org/10.1016/j.tcs.2019.12.003 doi: 10.1016/j.tcs.2019.12.003 |
[4] | Z. R. Zheng, X. Y. Liu, L. Z. Yin, Z. C. Liu, A hybrid password authentication scheme based on shape and text, J. Comput., 5 (2010), 765–772. https://doi.org/10.4304/jcp.5.5.765-772 doi: 10.4304/jcp.5.5.765-772 |
[5] | Y. Z. Tian, L. X. Li, H. P. Peng, Y. X. Yang, Achieving flatness: Graph labelling can generate graphical honeywords, Comput. Secur., 104 (2021), 102212. https://doi.org/10.1016/j.cose.2021.102212 doi: 10.1016/j.cose.2021.102212 |
[6] | W. Chen, J. Li, Z. Huang, C. Z. Gao, S. M. Yiu, Lattice-based unidirectional infinite-use proxy resignatures with private re-signature key, J. Comput. Syst. Sci., 120 (2021), 137–148. https://doi.org/10.1016/j.jcss.2021.03.008 doi: 10.1016/j.jcss.2021.03.008 |
[7] | X. Zhang, C. Ye, S. Zhang, B. Yao, Graph colorings and labelings having multiple restrictive conditions in topological coding, Mathematics, 10 (2022), 1592. https://doi.org/10.3390/math10091592 doi: 10.3390/math10091592 |
[8] | J. Sedlacek, Problem 27, Theory of graphs and its applications, Proc Symp Smolenice, Praha: Academia, 1963, 163–169. |
[9] | G. S. Bloom, S. W. Golomb, Numbered complete graphs, unusual rules, and assorted applications, In: Theory and Applications of Graphs, 2006, 53–65. https://doi.org/10.1007/BFb0070364 |
[10] | W. D. Wallis, Magic graphs, Berlin: Birkh-auser, 2001. |
[11] | H. Y. Wang, J. Xu, B. Yao, Exploring new cryptographical construction of complex network data, In: 2016 IEEE First International Conference on Data Science in Cyberspace(DSC), 2016, 155–160. https://doi.org/10.1109/DSC.2016.76 |
[12] | H. Y. Wang, J. Xu, B. Yao, The key-models and their lock-models for designing new labellings of networks, In: 2016 IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC), 2016, 565–568. https://doi.org/10.1109/IMCEC.2016.7867273 |
[13] | B. Yao, M. M. Zhao, X. H. Zhang, Y. R. Mu, Y. R. Sun, Topological coding and topological matrices toward network overall security, arXiv preprint, 2019. https://doi.org/10.48550/arXiv.1909.01587 |
[14] | J. A. Bondy, U. S. R. Murty, Graph theory with applications, MacMillan Press Ltd., 1976. |
[15] | J. A. Gallian, A dynamic survey of graph labelling, 23 Eds., Electron. J. Comb., 2020. |