Bipartite graphs are weak antimagic

arXiv1306.1763MaRDI QIDQ6242519FDOQ6242519

Authors: Matthias Beck, Michael Jackanich 

Publication date: 7 June 2013

Abstract: The emph{Antimagic Graph Conjecture} asserts that every connected graph $G=(V,E)$ except $K_2$ admits an edge labeling such that each label $1,2,\mathrm{...},|E|$ is used exactly once and the sums of the labels on all edges incident with a given node are distinct. We study an associated counting function (replacing the upper bound on the possible labels by a variable) and prove that a variant of this counting function, when we do not require the labels to be distinct, is a polynomial if $G$ is bipartite. As a consequence, we show that every connected bipartite graph $G=(V,E)$ except $K_2$ admits a emph{weakly} antimagic labeling, that is, each edge label is among $1,2,\mathrm{...},|E|$ (repetition allowed) and the sums of the labels on all edges incident with a given node are distinct. We also present a natural extension of these results to directed and bidirected graphs; this extension gives rise to a (bi-)directed version of the Antimagic Graph Conjecture, which might be of independent interest.

Mathematics Subject Classification ID

Graph polynomials (05C31) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Signed and weighted graphs (05C22) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

This page was built for publication: Bipartite graphs are weak antimagic

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