TY - JOUR
T1 - Weighted-1-antimagic graphs of prime power order
AU - Huang, Po Yi
AU - Wong, Tsai Lien
AU - Zhu, Xuding
PY - 2012/7/28
Y1 - 2012/7/28
N2 - 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→N, there is an injection f:E→1,2,⋯,|E|+k such that for any two distinct vertices u and v, ∑e∈E(v)f(e)+w(v)≠∑e∈E(u)f(e)+w(u). There are connected graphs G≠K2 which are not weighted-1-antimagic. It was asked in Wong and Zhu (in press) [13] whether every connected graph other than K2 is weighted-2-antimagic, and whether every connected graph on an odd number of vertices is weighted-1-antimagic. It was proved in Wong and Zhu (in press) [13] 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 pz 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 pz, p≠3 and has maximum degree at least |V(G)|-3, then G is weighted-1-antimagic.
AB - 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→N, there is an injection f:E→1,2,⋯,|E|+k such that for any two distinct vertices u and v, ∑e∈E(v)f(e)+w(v)≠∑e∈E(u)f(e)+w(u). There are connected graphs G≠K2 which are not weighted-1-antimagic. It was asked in Wong and Zhu (in press) [13] whether every connected graph other than K2 is weighted-2-antimagic, and whether every connected graph on an odd number of vertices is weighted-1-antimagic. It was proved in Wong and Zhu (in press) [13] 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 pz 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 pz, p≠3 and has maximum degree at least |V(G)|-3, then G is weighted-1-antimagic.
UR - http://www.scopus.com/inward/record.url?scp=84860887586&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860887586&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2011.09.019
DO - 10.1016/j.disc.2011.09.019
M3 - Article
AN - SCOPUS:84860887586
SN - 0012-365X
VL - 312
SP - 2162
EP - 2169
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 14
ER -