The direct product of a star and a path is antimagic

Abstract

A graph $G$ is antimagic if there exists a bijection $f$ from $E(G)$ to $\left\{1,2, \dots,|E(G)|\right\}$ such that the vertex sums for all vertices of $G$ are distinct, where the vertex sum is defined as the sum of the labels of all incident edges. Hartsfield and Ringel conjectured that every connected graph other than $K_2$ admits an antimagic labeling. It is still a challenging problem to address antimagicness in the case of disconnected graphs. In this paper, we study antimagicness for the disconnected graph that is constructed as the direct product of a star and a path.

Keywords

• direct product
• star
• path
• disconnected graph
• antimagic labeling

Supporting Institution

Slovak Research and Development Agency

Project Number

APVV-19-0153 and VEGA 1/0243/23

Thanks

Slovak Research and Development Agency

References

1. [1] N. Alon, G. Kaplan, A. Lev, Y. Roditty and R. Yuster, Dense graphs are antimagic, J. Graph Theory 47 (4), 297–309, 2004.
2. [2] M. Baca, O. Phanalasy, J. Ryan and A. Semanicová-Fenovcíková, Antimagic labelings of join graphs, Math. Comput. Sci. 9 (2), 139–143, 2015.
3. [3] Z.C. Chen, K.C. Huang, C. Lin, J.L. Shang and M.J. Lee, Antimagicness of star forests, Util. Math. 114, 283–294, 2020.
4. [4] Y. Cheng, Lattice grids and prims are antimagic, Theor. Comput. Sci. 374 (1-3), 66–73, 2007.
5. [5] Y. Cheng, A new class of antimagic Cartesian product graphs, Discret. Math. 308 (24), 6441–6448, 2008.
6. [6] J.W. Daykin, C.S. Iliopoulos, M. Miller and O. Phanalasy, Antimagicness of generalized corona and snowflake graphs, Math. Comput. Sci. 9, 105–111, 2015.
7. [7] N. Hartsfield and G. Ringel, Pearls in Graph Theory: A Comprehensive Introduction, Academic Press: Boston, MA, USA, 1990
8. [8] Y.C. Liang and X. Zhu, Anti-magic labelling of Cartesian product of graphs, Theor. Comput. Sci. 477, 1–5, 2013.

9. [9] Y. Lu, G. Dong, W. Ma and N. Wang, Antimagic labeling of the lexicographic product graph $K_{m,m} \left[P_k\right]$, Math. Comput. Sci. 12, (1), 77–90, 2018.
10. [10] Y. Lu, G. Dong and N. Wang, Antimagicness of Lexicographic product graph $G\left[P_n\right]$, Acta Math. Appl. Sin. Engl. Ser. 36, (3), 603–619, 2020.
11. [11] W. Ma, G. Dong, Y. Lu and N. Wang, Lexicographic product graphs $P_m \left[P_n\right]$ are antimagic, AKCE Int. J. Graphs Comb. 15, (3), 271–283, 2018.
12. [12] O. Phanalasy, M. Miller, C.S. Iliopoulos, S.P. Pissis and E. Vaezpour, Construction of antimagic labeling for the Cartesian product of regular graphs, Math. Comput. Sci. 5 (1), 81–87, 2011.
13. [13] E. Sampathkumar, On tensor product of graphs, J. Aust. Math. Soc. 20 (3), 268–273, 1975.
14. [14] J.-L. Shang, $P_2$, $P_3$, $P_4$-free linear forests are antimagic, Util. Math. 101, 13–22, 2016.
15. [15] J.-L. Shang, C. Lin and S.C. Liaw, On the antimagic labeling of star forests, Util. Math. 97, 373–385, 2015.
16. [16] T.M.Wang and C.C. Hsiao, On anti-magic labeling for graph products, Discret. Math. 308 (16), 3624–3633, 2008.
17. [17] T. Wang, M. Liu and D. Li, Some classes of disconnected antimagic graphs and their joins, Wuhan Univ. J. Nat. Sci. 17, 195–199, 2012.
18. [18] T. Wang, M.J. Liu and D.M. Li, A class of antimagic join graphs, Acta Math. Sin. Engl. Ser. 29, (5), 1019–1026, 2013.
19. [19] P.M. Weichsel, The Kronecker product of graphs, Proc. Am. Math. Soc. 13, 47–52, 1963.
20. [20] Z.B. Yilma, Antimagic properties of graphs with large maximum degree, J. Graph Theory 72, (4), 367–373, 2013.