Premium
Zero‐sum block designs and graph labelings
Author(s) -
Tuza Zsolt
Publication year - 1995
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.3180030203
Subject(s) - combinatorics , mathematics , modulo , conjecture , graph , statement (logic) , discrete mathematics , binary number , block (permutation group theory) , enhanced data rates for gsm evolution , arithmetic , computer science , telecommunications , political science , law
Proving a conjecture of Aigner and Triesch, we show that every graph G = ( V,E ) without isolated vertices and isolated edges admits an edge labeling ξ: E → {0,1} m with binary vectors of length m = [log 2 n ] + 1 such that the sums. CALLING STATEMENT : (taken modulo 2 componentwise) are mutually distinct, provided that n is sufficiently large. The proof combines probabilistic arguments with explicitly constructed Steiner systems. © 1995 John Wiley & Sons, Inc.