✦ LIBER ✦

Dense graphs are antimagic

✍ Scribed by N. Alon; G. Kaplan; A. Lev; Y. Roditty; R. Yuster

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 118 KB
Volume: 47
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20027

No coin nor oath required. For personal study only.

✦ Synopsis

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 called antimagic if it has an antimagic labeling. A conjecture of Ringel (see 4) states that every connected graph, but K~2~, is antimagic. Our main result validates this conjecture for graphs having minimum degree Ω (log n). The proof combines probabilistic arguments with simple tools from analytic number theory and combinatorial techniques. We also prove that complete partite graphs (but K~2~) and graphs with maximum degree at least n – 2 are antimagic. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 297–309, 2004

📜 SIMILAR VOLUMES

Regular bipartite graphs are antimagic

✍ Daniel W. Cranston 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## 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__.

On antimagic directed graphs

✍ Dan Hefetz; Torsten Mütze; Justus Schwartz 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

## Abstract An antimagic labeling of an undirected graph __G__ with __n__ vertices and __m__ edges is a bijection from the set of edges of __G__ 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 th

Antimagic labelling of vertex weighted g

Antimagic labelling of vertex weighted graphs

✍ Tsai-Lien Wong; Xuding Zhu 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

## Abstract Suppose __G__ is a graph, __k__ is a non‐negative integer. We say __G__ is __k__‐antimagic if there is an injection __f__: __E__→{1, 2, …, |__E__| + __k__} such that for any two distinct vertices __u__ and __v__, . We say __G__ is weighted‐__k__‐antimagic if for any vertex weight functi

Packing and covering dense graphs

✍ Noga Alon; Yair Caro; Raphael Yuster 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB 👁 1 views

Irregularity strength of dense graphs

✍ Bill Cuckler; Felix Lazebnik 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract Let __G__ be a simple graph of order __n__ with no isolated vertices and no isolated edges. For a positive integer __w__, an assignment __f__ on __G__ is a function __f__: __E__(__G__) → {1, 2,…, __w__}. For a vertex __v__, __f__(__v__) is defined as the sum __f__(__e__) over all edges

Dense Graphs with Cycle Neighborhoods

✍ A. Seress; T. Szabo 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 420 KB

For all \(\varepsilon>0\), we construct graphs with \(n\) vertices and \(>n^{2-n}\) edges, for arbitrarily large \(n\), such that the neighborhood of each vertex is a cycle. This result is asymptotically best possible. "1995 Academic Press. Inc.