Sponsored by the Rutgers University Department of Mathematics and the

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

**Co-organizers:****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

Abstract:

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 K_{2} 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.