Minimum-weight edge discriminators in hypergraphs

Authors Bhaswar B. Bhattacharya, Sayantan Das, Shirshendu Ganguly

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4668, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p18

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph labeling hypergraphs irregular network

Mathematics Subject Classification ID

Paths and cycles (05C38) Hypergraphs (05C65) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Combinatorial optimization (90C27)

Abstract: In this paper we introduce the concept of minimum-weight edge-discriminators in hypergraphs, and study its various properties. For a hypergraph

m a t h c a l H = (m a t h c a l V, m a t h c a l E)

, a function

l a m b d a : m a t h c a l V i g h t a r r o w m a t h b b Z^{+} c u p 0

is said to be an {it edge-discriminator} on

m a t h c a l H

if

s u m_{v i n E_{i}} l a m b d a (v) > 0

, for all hyperedges

E_{i} i n m a t h c a l E

, and

s u m_{v i n E_{i}} l a m b d a (v) e s u m_{v i n E_{j}} l a m b d a (v)

, for every two distinct hyperedges

E_{i}, E_{j} i n m a t h c a l E

. An {it optimal edge-discriminator} on

m a t h c a l H

, to be denoted by

l a m b d a_{m} a t h c a l H

, is an edge-discriminator on

m a t h c a l H

satisfying

s u m_{v i n m a t h c a l V} l a m b d a_{m} a t h c a l H (v) = m i n_{l} a m b d a s u m_{v i n m a t h c a l V} l a m b d a (v)

, where the minimum is taken over all edge-discriminators on

m a t h c a l H

. We prove that any hypergraph

m a t h c a l H = (m a t h c a l V, m a t h c a l E)

, with

| m a t h c a l E | = n

, satisfies

s u m_{v i n m a t h c a l V} l a m b d a_{m} a t h c a l H (v) l e q n (n + 1) / 2

, and equality holds if and only if the elements of

m a t h c a l E

are mutually disjoint. For

r

-uniform hypergraphs

m a t h c a l H = (m a t h c a l V, m a t h c a l E)

, it follows from results on Sidon sequences that

s u m_{v i n m a t h c a l V} l a m b d a_{m a t h c a l H} (v) l e q | m a t h c a l V |^{r + 1} + o (| m a t h c a l V |^{r + 1})

, and the bound is attained up to a constant factor by the complete

r

-uniform hypergraph. Next, we construct optimal edge-discriminators for some special hypergraphs, which include paths, cycles, and complete

r

-partite hypergraphs. Finally, we show that no optimal edge-discriminator on any hypergraph

m a t h c a l H = (m a t h c a l V, m a t h c a l E)

, with

| m a t h c a l E | = n (g e q 3)

, satisfies

s u m_{v i n m a t h c a l V} l a m b d a_{m} a t h c a l H (v) = n (n + 1) / 2 - 1

, which, in turn, raises many other interesting combinatorial questions.

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.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Minimum-weight edge discriminators in hypergraphs

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