Title page for etd-0010114-155910


[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
  • etd-0010114-155910.pdf
  • indicate access worldwide
    Date of Submission 2014-01-13

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys