Premium
Score sequences of oriented graphs
Author(s) -
Avery Peter
Publication year - 1991
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190150303
Subject(s) - mathematics , combinatorics , tournament , sequence (biology) , transitive relation , graph , discrete mathematics , biology , genetics
We extend Landau's concept of the score structure of a tournament to that of the score sequence of an oriented graph, and give a condition for an arbitrary integer sequence to be a score sequence. The proof is by construction of a specific oriented graph Δ( S ) with given score sequence S . It is shown that Δ( S ) is transitive and has the minimum number of arcs among the oriented graphs with score sequence S .