✦ LIBER ✦

Score sequences of oriented graphs

✍ Scribed by Peter Avery

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 349 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150303

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

📜 SIMILAR VOLUMES

On the oriented chromatic index of orien

On the oriented chromatic index of oriented graphs

✍ Pascal Ochem; Alexandre Pinlou; Éric Sopena 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

## Abstract A homomorphism from an oriented graph __G__ to an oriented graph __H__ is a mapping $\varphi$ from the set of vertices of __G__ to the set of vertices of __H__ such that $\buildrel {\longrightarrow}\over {\varphi (u) \varphi (v)}$ is an arc in __H__ whenever $\buildrel {\longrightarrow}

Oriented list colorings of graphs

✍ Zs. Tuza; M. Voigt 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB 👁 1 views

A 2-assignment on a graph G (V,E) is a collection of pairs Lv of allowed colors speci®ed for all vertices v PV. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satis®es the following property: For every 2-assignment there exists a choic

Underlying properties of oriented graphs

✍ T. A. McKee 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 361 KB

Generalized Pigeonhole Properties of Gra

Generalized Pigeonhole Properties of Graphs and Oriented Graphs

✍ Anthony Bonato; Peter J Cameron; Dejan Delić; Stéphan Thomassé 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

A relational structure A satisfies the P(n, k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is isomorphic to A. The P(2, 1) property is just the pigeonhole property, (P), introduced by Cameron, and studied

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

Signed degree sequences of signed graphs

✍ Yan, Jing-Ho; Lih, Ko-Wei; Kuo, David; Chang, Gerard J. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

sequence to be the signed degree sequence of a signed graph or a signed tree, answering a question raised by