[Back to Results | New Search]

URN etd-0010114-155910 Author Yu-Chang Liang Author's Email Address chase2369219@hotmail.com Statistics This thesis had been viewed 5538 times. Download 1090 times. Department Applied Mathematics Year 2013 Semester 1 Degree Ph.D. Type of Document Language English Title Anti-magic labeling of graphs Date of Defense 2013-11-24 Page Count 95 Keyword regular graph tree anti-magic Cartesian product graph Abstract An antimagic labeling of a graph G is a one-to-one correspondence between

E(G) and {1, 2, . . . , |E|} such that for any two distinct vertices u and

v, the sum of the labels assigned to edges incident to u is distinct from the

sum of the labels assigned to edges incident to v. It was conjectured by

Hartsfield and Ringel [9] in 1990 that every connected graph other than K2

has an antimagic labeling. This conjecture attracted considerable attention.

It has been verified for many special classes of graphs, such as paths, cycles,

wheels, complete graphs, dense graphs, graphs with maximum degree

≥ |V (G)| − 2, regular bipartite graphs, trees with at most one vertex of

degree 2, graphs of order pk containing a Cp-factor for some prime number p,

and the Cartesain product of paths, cycles, the Cartesian product of an arbitrary

graph with a antimagic regular graph, etc. Nevertheless, the conjecture

remained largely open.

In Chapter 2, we study antimagic labeling of regular graphs. It is proved

that if k is an odd integer, then every k-regular graph is antimagic. For

an even integer k, a sufficient condition is given for a k-regular graph to be

antimagic.

In Chapter 3, we study antimagic labeling of trees. It was proved in [12]

that if a tree T has at most one degree 2 vertex, then T is antimagic. The

proof contains a minor error. We first correct this error. Then we study trees

which contains more degree 2 vertices. Let V2 be the set of degree 2 vertices

of T. We prove that if V2 and V V2 are both independent sets, then T is

antimagic. We also prove that if the set of even degree vertices induces a

path, then T is antimagic.

In Chapter 4, we study antimagic labeling of Cartesian product of graphs.

It was proved in [25] that if G is an antimagic regular graph, then for any

graph H, G2H is antimagic. We strengthen this result by not requiring G

to be antimagic. We prove that if G is k-regular for k ≥ 2, and H 6= K1 is a connected graph, then the Cartesian product H2G is antimagic. Observe

that G2K1 is the graph G itself. So the condition that H 6= K1 is natural.

If G is 1-regular and connected, then G = K2 and K22H is called the prism

of H. We prove that if a connected graph H has at least one vertex of odd degree, then the prism of H is antimagic; if H has at least 2|V (H)| − 2 edges, then the prism of H is also antimagic. Not much is known about the Cartesian product of two non-regular graphs. We prove that if each of G1 and G2 is obtained from a regular graph by adding a universal vertex, then the Cartesian product G12G2 and the Cartesian powers of Gi are both antimagic. We also prove that if G1 and G2 are double stars, then G12G2 is antimagic.Advisory Committee Ko-Wei Lih - chair

D. J. Guan - co-chair

Gerard Jennhwa Chang - co-chair

Sen-Peng Eu - co-chair

Tsai-Lien Wong - co-chair

Yeong-Nan Yeh - co-chair

Hong-Gwa Yeh - co-chair

Li-Da Tong - co-chair

Xuding Zhu - advisor

Files indicate access worldwide

etd-0010114-155910.pdf Date of Submission 2014-01-13