×

The antimagicness of the Cartesian product of graphs. (English) Zbl 1162.05042

Summary: An antimagic labeling of a graph with \(M\) edges and \(N\) vertices is a bijection from the set of edges to the set \(\{1,2,3,\dots ,M\}\) such that all the \(N\) vertex-sums are pairwise distinct, where the vertex-sum of a vertex \(v\) is the sum of labels of all edges incident with \(v\). A graph is called antimagic if it has an antimagic labeling. The antimagicness of the Cartesian product of graphs in several special cases has been studied [T.-M. Wang, “Toroidal grids are anti-magic”, Lect. Notes Comput. Sci. 3595, 671–679 (2005; Zbl 1128.05311); Y. Cheng, “A new class of antimagic Cartesian product graphs”, Discrete Math. 308, No. 24, 6441–6448 (2008; Zbl 1211.05140)]. In this paper, we develop new construction methods that are applied to more general cases. We prove that the Cartesian product of paths is antimagic, if one of them has at least three edges. This (almost) answers the open problems in [Y. Cheng, “Lattice grids and prisms are antimagic”, Theor. Comput. Sci. 374, No. 1–3, 66–73 (2007; Zbl 1162.05040)]. We also prove that the Cartesian product of an antimagic regular graph and a connected graph is antimagic, which extends the results of the latter of the two references, where several special cases are studied.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI

References:

[1] Alon, N.; Kaplan, G.; Lev, A.; Roditty, Y.; Yuster, R., Dense graphs are antimagic, Journal of Graph Theory, 47, 297-309 (2004) · Zbl 1055.05132
[2] Cheng, Yongxi, Lattice grids and prisms are antimagic, Theoretical Computer Science, 374, 66-73 (2007) · Zbl 1162.05040
[3] Cheng, Yongxi, A new class of antimagic cartesian product graphs, Discrete Mathematics, 308, 24, 6441-6448 (2008) · Zbl 1211.05140
[4] Daniel Cranston, Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem; Daniel Cranston, Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem
[5] Hartsfield, N.; Ringel, G., Pearls in Graph Theory (1990), Academic Press, INC: Academic Press, INC Boston, (Revised version, 1994), pp. 108-109 · Zbl 0703.05001
[6] Hefetz, Dan, Antimagic graphs via the combinatorial NullStellenSatz, Journal of Graph Theory, 50, 263-272 (2005) · Zbl 1076.05068
[7] Wang, Tao-Ming, Toroidal grids are anti-magic, (Proc. 11th Annual International Computing and Combinatorics Conference. Proc. 11th Annual International Computing and Combinatorics Conference, COOCOON’2005. Proc. 11th Annual International Computing and Combinatorics Conference. Proc. 11th Annual International Computing and Combinatorics Conference, COOCOON’2005, LNCS, vol. 3595 (2005), Springer), 671-679 · Zbl 1128.05311
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.