betaFeedback

WorksMathematics

The isolation number of uniform hypertrees

Abstract

An isolating set of a hypergraph HH is a vertex set whose closed neighbourhood intersects every edge of HH. The isolation number ι(H)ι(H) is the minimum cardinality of such a set. Let r≥3r\ge3, and let TT be an rr-uniform hypergraph whose incidence graph is a tree. We prove that, if TT has order nn and at least two edges, then ι(T)≤⌊n/(2r−1)⌋ι(T)\le\lfloor n/(2r-1)\rfloor. The bound is attained at every admissible order. We characterize all hypertrees attaining it by a construction using six types of marked hypertrees of orders 2r−12r-1, 3r−23r-2 and 4r−34r-3. The proof uses a packing formula for the isolation number and an exact identity for the difference n−(2r−1)ι(T)n-(2r-1)ι(T). For connected graphs of order nn with at least two blocks, all of which are triangles, we obtain the sharp bound ⌊n/5⌋\lfloor n/5\rfloor on the cycle isolation number and characterize the graphs attaining it.

Paper details

vlnc:W_puqc4k89
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…