Minimum-weight edge discriminators in hypergraphs

MaRDI QIDQ405305zbMATH OpenFDO

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

hypergraphsgraph labelingirregular network

Mathematics Subject Classification ID

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

Abstract: In this paper we introduce the concept of minimum-weight edge-discriminators in hypergraphs, and study its various properties. For a hypergraph $mathcalH=(mathcalV,mathcalE)$, a function $lambda:mathcalVightarrowmathbb{Z}^{+}cup0$ is said to be an {it edge-discriminator} on $mathcalH$ if $su{m}_{vin{E}_i}lambda(v)>0$, for all hyperedges $E_{i}inmathcalE$, and $su{m}_{vin{E}_i}lambda(v)esu{m}_{vin{E}_j}lambda(v)$, for every two distinct hyperedges $E_i,E_{j}inmathcalE$. An {it optimal edge-discriminator} on $mathcalH$, to be denoted by $lambd{a}_{m}athcalH$, is an edge-discriminator on $mathcalH$ satisfying $su{m}_{vinmathcalV}lambd{a}_{m}athcalH(v)=mi{n}_{l}ambdasu{m}_{vinmathcalV}lambda(v)$, where the minimum is taken over all edge-discriminators on $mathcalH$. We prove that any hypergraph $mathcalH=(mathcalV,mathcalE)$, with $|mathcalE|=n$, satisfies $su{m}_{vinmathcalV}lambd{a}_{m}athcalH(v)leqn(n+1)/2$, and equality holds if and only if the elements of $mathcalE$ are mutually disjoint. For $r$-uniform hypergraphs $mathcalH=(mathcalV,mathcalE)$, it follows from results on Sidon sequences that $su{m}_{vinmathcalV}lambd{a}_{mathcalH}(v)leq|mathcalV{|}^{r+1}+o(|mathcalV{|}^{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 $mathcalH=(mathcalV,mathcalE)$, with $|mathcalE|=n(geq3)$, satisfies $su{m}_{vinmathcalV}lambd{a}_{m}athcalH(v)=n(n+1)/2-1$, which, in turn, raises many other interesting combinatorial questions.

Recommendations

• The 1-2-3-conjecture for hypergraphs
• Determining and distinguishing number of hypergraphs
• scientific article; zbMATH DE number 4095516
• Sum-distinguishing number of sparse hypergraphs
• On special numberings of hypergraphs

Cites work

• scientific article; zbMATH DE number 3121715 (Why is no real title available?)
• scientific article; zbMATH DE number 4139798 (Why is no real title available?)
• scientific article; zbMATH DE number 4142086 (Why is no real title available?)
• scientific article; zbMATH DE number 3784967 (Why is no real title available?)
• scientific article; zbMATH DE number 49909 (Why is no real title available?)
• scientific article; zbMATH DE number 89403 (Why is no real title available?)
• scientific article; zbMATH DE number 1833076 (Why is no real title available?)
• scientific article; zbMATH DE number 867641 (Why is no real title available?)
• B _h [ g ] sequences
• A Tight Bound on the Irregularity Strength of Graphs
• A complete annotated bibliography of work related to Sidon sequences
• A construction for sets of integers with distinct subset sums
• A dynamic survey of graph labeling
• A new upper bound for the irregularity strength of graphs
• A remark on \(B_{2k}\)-sequences
• An improved lower bound on the greatest element of a sum-distinct set of fixed order
• An inequality for B2-sequences
• Integer Sets with Distinct Subset-Sums
• Integer sets with prescribed pairwise differences being distinct
• Irregular networks, regular graphs and integer matrices with distinct row and column sums
• Irregularity strength of regular graphs
• Linear bound on the irregularity strength and the total vertex irregularity strength of graphs
• Minimum-weight edge discriminators in hypergraphs
• New upper bounds for finite \(B_h\) sequences
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On graph irregularity strength
• Sets of Integers Whose Subsets Have Distinct Sums
• Sidon sets in \(\mathbb N^d\)
• Siegel's Lemma and sum-distinct sets
• Theorems in the additive theory of numbers

Cited in

(2)

• Minimum-weight edge discriminators in hypergraphs
• Sum-distinguishing number of sparse hypergraphs

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)