×

On antimagic labeling of regular graphs with particular factors. (English) Zbl 1334.05157

Summary: An antimagic labeling of a finite simple undirected graph with \(q\) edges is a bijection from the set of edges to the set of integers \(\{1,2,\dots,q\}\) such that the vertex sums are pairwise distinct, where the vertex sum at vertex \(u\) is the sum of labels of all edges incident to such vertex. A graph is called antimagic if it admits an antimagic labeling. It was conjectured by N. Hartsfield and G. Ringel in 1990 that all connected graphs besides \(K_2\) are antimagic. Another weaker version of the conjecture is every regular graph is antimagic except \(K_2\). Both conjectures remain unsettled so far. In this article, we focus on antimagic labeling of regular graphs. Certain classes of regular graphs with particular factors are shown to be antimagic. Note that the results here are also valid for regular multi-graphs.

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, 4, 297-309 (2004) · Zbl 1055.05132
[2] Bača, M.; Jendrol, S.; Miller, M.; Ryan, J., Antimagic labelings of generalized Petersen graphs that are plane, Ars Combinatoria (2004) · Zbl 1072.05050
[3] Barrus, M. D., Antimagic labeling and canonical decomposition of graphs, Information Processing Letters, 110, 7, 261-263 (2010) · Zbl 1197.05124
[4] Cheng, Y., Lattice grids and prisms are antimagic, Theoretical Computer Science, 374, 1-3, 66-73 (2007) · Zbl 1162.05040
[5] Cheng, Y., A new class of antimagic Cartesian product graphs, Discrete Mathematics, 308, 24, 6441-6448 (2008) · Zbl 1211.05140
[6] Cranston, D., Regular bipartite graphs are antimagic, Journal of Graph Theory, 60, 3, 173-182 (2009) · Zbl 1210.05141
[7] Gallian, J. A., A dynamic survey of graph labeling, The Electronic Journal of Combinatorics, 18 (2011), DS6, November 17, 2011
[8] Hartsfield, N.; Ringel, G., Pearls in Graph Theory, 108-109 (1990), Academic Press, Inc.: Academic Press, Inc. Boston, (revised version 1994) · Zbl 0703.05001
[9] Hefetz, D., Anti-magic graphs via the combinatorial nullstellensatz, Journal of Graph Theory, 50, 4, 263-272 (2005) · Zbl 1076.05068
[10] Hefetz, D.; Mutze, T.; Schwartz, J., On antimagic directed graphs, Journal of Graph Theory, 64, 3, 219-232 (2010) · Zbl 1209.05213
[11] Hefetz, D.; Saluz, A.; Tran, H. T.T., An application of the combinatorial Nullstellensatz to a graph labelling problem, Journal of Graph Theory, 65, 1, 70-82 (2009) · Zbl 1209.05214
[12] Huang, P. Y.; Wong, T. L.; Zhu, X., Weighted-1-antimagic graphs of prime power order, Discrete Mathematics, 312, 14, 2162-2169 (2011) · Zbl 1244.05186
[13] Ivančo, J.; Semaničová, A., Some constructions of supermagic graphs using antimagic graphs, SUT J. Math., 42, 2, 177-186 (2006) · Zbl 1136.05065
[14] Lee, M.; Lin, C.; Tsai, W., On antimagic labeling for power of cycles, Ars Combinatoria, 98, 161-165 (2011) · Zbl 1249.05338
[15] Liang, Y. C.; Zhu, X., Antimagic labeling of cubic graphs, Journal of Graph Theory (2013)
[16] Miller, M.; Bača, M., Antimagic valuations of generalized Petersen graphs, Australasian Journal of Combinatorics, 22, 135-139 (2000) · Zbl 0971.05098
[17] Wang, T. M., Toroidal grids are antimagic, Lecture Notes in Computer Science (LNCS), 3595, 671-679 (2005) · Zbl 1128.05311
[18] Wang, T. M.; Hsiao, C. C., On antimagic labeling for graph products, Discrete Mathematics, 308, 3624-3633 (2008) · Zbl 1155.05055
[19] Wang, T. M.; Hsiao, C. C.; Lee, S. M., A note on edge-graceful spectra of the square of paths, Discrete Mathematics, 308, 5878-5885 (2008) · Zbl 1180.05066
[20] Wang, T. M.; Zhang, G. H., On antimagic labeling for odd regular graphs, (Arumugam, S.; Smyth, B., IWOCA 2012. IWOCA 2012, Tamil Nadu, India. IWOCA 2012. IWOCA 2012, Tamil Nadu, India, Lecture Notes in Computer Science (LNCS), vol. 7643 (2012)), 162-168 · Zbl 1293.05345
[22] Wong, T. L.; Zhu, X., Antimagic labelling of vertex weighted graphs, Journal of Graph Theory, 70, 3, 348-350 (2011) · Zbl 1244.05192
[23] Yilma, Z. B., Antimagic properties of graphs with large maximum degree, Journal of Graph Theory (2012)
[24] Zhang, Y.; Sun, X., The antimagicness of the Cartesian product of graphs, Theoretical Computer Science, 410, 727-735 (2009) · Zbl 1162.05042
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.