Score sequences in oriented k-hypergraphs

Shariefuddin Pirzada, Zhou Guofei

Abstract

Given two non-negative integers n and k with n≥ k>1, an oriented k-hypergraph on n vertices is a pair (V,A), where V is a set of vertices with |V| =n and A is a set of k-tuples of vertices, called arcs, such that for any k-subset S of V, A contains at most one of the k! k-tuples whose entries belong to S.

In this paper, we define the score of a vertex in an oriented k-hypergraph and then give a necessary and sufficient condition for the sequence of non-negative integers [s₁ , s₂ , …, sn] to be a score sequence of some oriented k-hypergraph.

Full Text:

PDF