### Title page for etd-0010114-155910

URN etd-0010114-155910 Yu-Chang Liang chase2369219@hotmail.com This thesis had been viewed 5538 times. Download 1090 times. Applied Mathematics 2013 1 Ph.D. English Anti-magic labeling of graphs 2013-11-24 95 regular graph tree anti-magic Cartesian product graph An antimagic labeling of a graph G is a one-to-one correspondence betweenE(G) and {1, 2, . . . , |E|} such that for any two distinct vertices u andv, the sum of the labels assigned to edges incident to u is distinct from thesum of the labels assigned to edges incident to v. It was conjectured byHartsfield and Ringel [9] in 1990 that every connected graph other than K2has 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 ofdegree 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 arbitrarygraph with a antimagic regular graph, etc. Nevertheless, the conjectureremained largely open.In Chapter 2, we study antimagic labeling of regular graphs. It is provedthat if k is an odd integer, then every k-regular graph is antimagic. Foran even integer k, a sufficient condition is given for a k-regular graph to beantimagic.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. Theproof contains a minor error. We first correct this error. Then we study treeswhich contains more degree 2 vertices. Let V2 be the set of degree 2 verticesof T. We prove that if V2 and V V2 are both independent sets, then T isantimagic. We also prove that if the set of even degree vertices induces apath, 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 anygraph H, G2H is antimagic. We strengthen this result by not requiring Gto 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. Observethat 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 prismof 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. 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 indicate access worldwide 2014-01-13

Browse | Search All Available ETDs