Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu
Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem

Speaker: Dan Cranston, DIMACS

Date: Thursday, October 11, 2007 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


A labeling of a graph is a bijection from its edge set to the set {1, 2,... , |E(G)|}. A labeling is antimagic if for every pair of distinct vertices u and v, the sum of the labels on edges incident to u is different from the sum of the labels on edges incident to v. We say a graph is antimagic if it has an antimagic labeling. In 1990, Ringel conjectured that every connected graph other than K2 is antimagic. The most significant progress was been made by Alon et al. (in 2004), who showed there exists a constant C, such that if an n-vertex graph G has δ(G)≥ Cn, then G is antimagic. In this paper, we show that every regular bipartite graph (with degree at least 2) is antimagic. Our technique relies heavily on the Marriage Theorem.