Minimum-weight edge discriminators in hypergraphs
type: Item
instance of: scholarly article
title: Minimum-weight edge discriminators in hypergraphs
zbMATH Open document ID: 1300.05193
author: Bhaswar B. Bhattacharya
author: Sayantan Das
author: Shirshendu Ganguly
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-04T00:00:00Z
full work available at URL: https://arxiv.org/abs/1210.4668
full work available at URL: v21i3p18
review text: Summary: In this paper we introduce the notion of minimum-weight edge-discriminators in hypergraphs, and study their various properties. For a hypergraph \(\mathcal H=(\mathcal V, \mathcal E)\), a function \(\lambda: \mathcal V\to \mathbb Z^{+}\cup\{0\}\) is said to be an edge-discriminator on \(\mathcal H\) if \(\sum_{v\in E_i}{\lambda(v)}0\), for all hyperedges \(E_i\in \mathcal E\), and \(\sum_{v\in E_i}{\lambda(v)}\neq \sum_{v\in E_j}{\lambda(v)}\), for every two distinct hyperedges \(E_i, E_j \in \mathcal E\). An optimal edge-discriminator on \(\mathcal H\), to be denoted by \(\lambda_\mathcal H\), is an edge-discriminator on \(\mathcal H\) satisfying \(\sum_{v\in \mathcal V}\lambda_\mathcal H (v)=\min_\lambda\sum_{v\in \mathcal V}{\lambda(v)}\), where the minimum is taken over all edge-discriminators on \(\mathcal H\). We prove that any hypergraph \(\mathcal H=(\mathcal V, \mathcal E)\), with \(|\mathcal E|=m\), satisfies \(\sum_{v\in \mathcal V} \lambda_\mathcal H(v)\leq m(m+1)/2\), and the equality holds if and only if the elements of \(\mathcal E\) are mutually disjoint. For \(r\)-uniform hypergraphs \(\mathcal H=(\mathcal V, \mathcal E)\), it follows from earlier results on Sidon sequences that \(\sum_{v\in \mathcal V}\lambda_{\mathcal H}(v)\leq |\mathcal V|^{r+1}+o(|\mathcal V|^{r+1})\), and the bound is attained up to a constant factor by the complete \(r\)-uniform hypergraph. Finally, we show that no optimal edge-discriminator on any hypergraph \(\mathcal H=(\mathcal V, \mathcal E)\), with \(|\mathcal E|=m~(\geq 3)\), satisfies \(\sum_{v\in \mathcal V} \lambda_\mathcal H (v)=m(m+1)/2-1\). This shows that all integer values between \(m\) and \(m(m+1)/2\) cannot be the weight of an optimal edge-discriminator of a hypergraph, and this raises many other interesting combinatorial questions.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6340242
zbMATH Keywords: graph labeling
zbMATH Keywords: hypergraphs
zbMATH Keywords: irregular network
MaRDI profile type: Publication
arXiv ID: 1210.4668
cites work: Siegel's Lemma and sum-distinct sets
cites work: A construction for sets of integers with distinct subset sums
cites work: Integer sets with prescribed pairwise differences being distinct
cites work: Theorems in the additive theory of numbers
cites work: Sidon sets in \(\mathbb N^d\)
cites work: New upper bounds for finite \(B_h\) sequences
cites work: B h [ g ] sequences
cites work: Q3472141
cites work: An improved lower bound on the greatest element of a sum-distinct set of fixed order
cites work: Q3234565
cites work: On a Problem of Sidon in Additive Number Theory, and on some Related Problems
cites work: Irregular networks, regular graphs and integer matrices with distinct row and column sums
cites work: Q3474681
cites work: On graph irregularity strength
cites work: A dynamic survey of graph labeling
cites work: Sets of Integers Whose Subsets Have Distinct Sums
cites work: Q4016824
cites work: Q3963072
cites work: A remark on \(B_{2k}\)-sequences
cites work: A New Upper Bound for the Irregularity Strength of Graphs
cites work: Q4873753
cites work: An inequality for B2-sequences
cites work: Integer Sets with Distinct Subset-Sums
cites work: A Tight Bound on the Irregularity Strength of Graphs
cites work: A complete annotated bibliography of work related to Sidon sequences
cites work: Q3999628
cites work: Irregularity strength of regular graphs
cites work: Linear Bound on the Irregularity Strength and the Total Vertex Irregularity Strength of Graphs
cites work: Q4780504
description: scientific article; zbMATH DE number 6340242