×

zbMATH — the first resource for mathematics

Weighted-1-antimagic graphs of prime power order. (English) Zbl 1244.05186
Summary: Suppose \(G\) is a graph, \(k\) is a non-negative integer. We say \(G\) is weighted-\(k\)-antimagic if for any vertex weight function \(w:V\to \mathbb N\), there is an injection \(f:E\to \{1,2,\dots ,\mid E\mid +k\}\) such that for any two distinct vertices \(u\) and \(v\),
\[ \sum _{e\in E(v)}f(e)+w(v)\neq \sum _{e\in E(u)}f(e)+w(u). \] There are connected graphs \(G\neq K_{2}\) which are not weighted-1-antimagic.
It was asked in T. Wong and X. Zhu [J. Graph Theory 70, No. 3, 348–350 (2012; Zbl 1244.05192)] whether every connected graph other than \(K_{2}\) is weighted-2-antimagic, and whether every connected graph on an odd number of vertices is weighted-1-antimagic. It was proved in T. Wong and X. Zhu [loc. cit] that if a connected graph \(G\) has a universal vertex, then \(G\) is weighted-2-antimagic, and moreover if \(G\) has an odd number of vertices, then \(G\) is weighted-1-antimagic.
In this paper, by restricting to graphs of odd prime power order, we improve this result in two directions: if \(G\) has odd prime power order \(p^{z}\) and has total domination number 2 with the degree of one vertex in the total dominating set not a multiple of \(p\), then \(G\) is weighted-1-antimagic. If \(G\) has odd prime power order \(p^{z}\), \(p \neq 3\) and has maximum degree at least \(|V(G)| - 3\), then \(G\) is weighted-1-antimagic.

MSC:
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C22 Signed and weighted graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Combinatorial nullstellensatz, Probability and computing, 8, 7-29, (1999) · Zbl 0920.05026
[2] 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
[3] Cheng, Y., Lattice grids and prisms are antimagic, Theoretical computer science, 374, 66-73, (2007) · Zbl 1162.05040
[4] Y. Cheng, Cartesian products of regular graphs are antimagic, arXiv:math/0602319v2 [math.CO].
[5] Hartsfield, N.; Ringel, G., Pearls in graph theory, (1990), Academic Press, Inc. Boston, pp. 108-109. Revised version 1994
[6] Hefetz, D., Anti-magic graphs via the combinatorial nullstellensatz, Journal of graph theory, 50, 263-272, (2005) · Zbl 1076.05068
[7] Hefetz, D.; Tran, H.T.T.; Saluz, A., An application of the combinatorial nullstellensatz to a graph labelling problem, Journal of graph theory, 65, 70-82, (2010), Published Online: 4 December 2009 · Zbl 1209.05214
[8] Kaplan, G.; Lev, A.; Roditty, Y., On zero-sum partitions and antimagic trees, Discrete mathematics, 309, 2010-2014, (2009) · Zbl 1229.05031
[9] Y. Liang, T. Wong, X. Zhu, Antimagic trees, manuscript, 2009.
[10] Scheim, D.E., The number of edge 3-colorings of a planar cubic graph as a permanent, Discrete mathematics, 8, 377-382, (1974) · Zbl 0281.05103
[11] Wang, T.M., Toroidal grids are antimagic, (), 671-679 · Zbl 1128.05311
[12] Wang, T.M.; Hsiao, C.C., On animagic labeling for graph products, Discrete mathematics, 308, 3624-3633, (2008) · Zbl 1155.05055
[13] T. Wong, X. Zhu, Antimagic labeling of vertex weighted graphs, Journal of Graph Theory, in press (doi:10.1002/jgt.20624). Published online: 22 July 2011.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.