Dense edge-magic graphs and thin additive bases

DOI10.1016/J.DISC.2006.05.003MaRDI QIDQ2501547zbMATH OpenOpenAlexFDO

Authors Oleg Pikhurko

Publication date 14 September 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0309029

zbMATH Keywords

quasi-Sidon setSidon setsum-set

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Other combinatorial number theory (11B75)

Abstract: We study s(k,n), the maximum size of A+A where A is a k-subset of [n]. A few known functions from additive number theory can be expressed via s(k,n). For example, our estimates of s(k,n) imply new bounds on the maximum size of quasi-Sidon sets, a problem posed by Erdos and Freud [J. Number Th.38 (1991) 196-205]. Also, applications to so-called edge-magic labellings of graphs are given.

Review text

An \((n,m)\)-graph is edge-magic if there is a labeling \(\ell:V(G)\cup E(G) \rightarrow \{1,2,\dots,n+m \}\) such that all the sums \(\ell(a) + \ell(ab) + \ell(b)\) are the same. Also, \(\mathcal{M}(n)\) is the maximum number of edges that a graph with \(n\) vertices can have. The paper presents new bounds on \(\mathcal{M}(n)\), namely: \[ \frac{2}{7} n^{2} + \mathrm{O}(n) \leq \mathcal{M}(n) \leq (0.489 \ldots +\mathrm{o}(1))n^{2} \] These calculations lead to a new bound on \(s(k,n)\), the maximum number of distinct pairwise sums that a \(k\)-subset of \(\{1,2, \dots , n\}\) can have, namely: \[ s(k,n) \leq n + k^{2} \left( \frac{1}{4}-\frac{1}{(\pi+2)^{2}} + \mathrm{o}(1)\right) \] These results have applications to the theory of quasi-Sidon sets as well.

Recommendations

• Bounds on the edge magic number for complete graphs
• On a question by Erdős about edge-magic graphs
• Strong edge-magic graphs of maximum size
• Some new bounds for edge-magic graphs
• On the edge-magic indices of (v,v+1)-graphs

Cites work

• A Survey of Problems in Combinatorial Number Theory
• Eine obere Schranke für die Reichweite einer Extremalbasis zweiter Ordnung.
• scientific article; zbMATH DE number 4085758 (Why is no real title available?)
• scientific article; zbMATH DE number 3784967 (Why is no real title available?)
• scientific article; zbMATH DE number 192902 (Why is no real title available?)
• scientific article; zbMATH DE number 1833076 (Why is no real title available?)
• Magic Valuations of Finite Graphs
• On a question by Erdős about edge-magic graphs
• On sums of a Sidon-sequence
• On the Cardinality of h -Bases for n
• On the representation of 1,2,..., n by sums
• The number of squares and \(B_h[g]\) sets
• Theorems in the additive theory of numbers
• Untere Schranken für die Reichweiten von Extremalbasen fester Ordnung
• Upper and lower bounds for finite \(B_h[g]\) sequences.
• Well distribution of Sidon sets in residue classes

Cited in

(3)

• On \(k\)-minimum and \(m\)-minimum edge-magic injections of graphs
• Integer sets with prescribed pairwise differences being distinct
• A new upper bound for finite additive h-bases

This page was built for publication: Dense edge-magic graphs and thin additive bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2501547)