✦ LIBER ✦

Regular bipartite graphs are antimagic

✍ Scribed by Daniel W. Cranston

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 94 KB
Volume: 60
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20347

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A labeling of a graph G is a bijection from E(G) to the set {1, 2,… |E(G)|}. A labeling is antimagic if for any 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, Hartsfield and Ringel conjectured that every connected graph other than K~2~ is antimagic. In this article, we show that every regular bipartite graph (with degree at least 2) is antimagic. Our technique relies heavily on the Marriage Theorem. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 173–182, 2009

📜 SIMILAR VOLUMES

Dense graphs are antimagic

✍ N. Alon; G. Kaplan; A. Lev; Y. Roditty; R. Yuster 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract An __antimagic labeling__ of graph a with __m__ edges and __n__ vertices is a bijection from the set of edges to the integers 1,…,__m__ such that all __n__ vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is c

Bipartite regular graphs with fixed diam

Bipartite regular graphs with fixed diameter

✍ H. J. Broersma; F. Göbel 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 420 KB

Tails of Bipartite Distance-regular Grap

Tails of Bipartite Distance-regular Graphs

✍ Michael S. Lang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 205 KB

Let denote a bipartite distance-regular graph with diameter D ≥ 4 and valency k ≥ 3. Let θ 0 > θ 1 > • • • > θ D denote the eigenvalues of and let E 0 , E 1 , . . . , E D denote the associated primitive idempotents. Fix s (1 ≤ s ≤ D -1) and abbreviate E := E s . We say E is a tail whenever the entry

Regular orientable embeddings of complet

Regular orientable embeddings of complete bipartite graphs

✍ Jin Ho Kwak; Young Soo Kwon 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph __K__~__n,n__~ are in one‐to‐one correspondence with the permutations on __n__ elements satisfying a given criterion, and the isomorphism classes of them are com

Spin Models on Bipartite Distance-Regula

Spin Models on Bipartite Distance-Regular Graphs

✍ K. Nomura 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 430 KB

Spin models were introduced by V. Jones (Pac. J. Math. 137 (1989), 311-336) to construct invariants of knots and links. A spin model will be defined as a pair \(S=(X, w)\) of a finite set \(X\) and a function \(w\) on \(X \times X\) satisfying several axioms. Some important spin models can be constr

Counting 1-Factors in Regular Bipartite

Counting 1-Factors in Regular Bipartite Graphs

✍ Alexander Schrijver 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 325 KB

We show that any k-regular bipartite graph with 2n vertices has at least \ (k&1) k&1 k k&2 + n perfect matchings (1-factors). Equivalently, this is a lower bound on the permanent of any nonnegative integer n\_n matrix with each row and column sum equal to k. For any k, the base (k&1) k&1 Âk k&2 is l