On the Cut-Vertex and the Interval Transit Functions of Hypergraphs
Ameera Vaheeda Shanavas, Manoj Changat, Peter Florian Stadler · Graphs and Combinatorics · 2024
Abstract Transit functions $$R:V\times V\rightarrow 2^V$$ R : V × V → 2 V model abstract betweenness as well as binary clustering. Examples are I(u, v), the interval between u and v, comprising all points on a shortest path from u to v, and C(u, v), the set of all cut vertices separating u and v together with u and v. Here we characterize the cut-vertex transit function of hypergraphs as the monotone transit functions satisfying (x) $$R(u,v)\subseteq R(u,x)\cup R(x,v)$$ R ( u , v ) ⊆ R ( u , x ) ∪ R ( x , v ) for all $$u,v,x\in V$$ u , v , x ∈ V . We define new hypergraph classes as restrictions and generalizations of linear hypergraphs and describe relevant properties of blocks and Berge cycles. We then show that the cut-vertex transit function coincides with the interval function exactly for linear B $$^*$$ ∗ -hypergraphs, generalizing a similar result for graphs. Moreover, we identify a subclass of block hypergraphs and characterize it using axioms on its interval function and prove a similar characterization for block graphs.