错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Cut-Vertex and the Interval Transit Functions of Hypergraphs

  • Ameera Vaheeda Shanavas,
  • Manoj Changat,
  • Peter F. Stadler

摘要

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(uv), the interval between u and v, comprising all points on a shortest path from u to v, and C(uv), 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.