✦ LIBER ✦

Degree frequencies in digraphs and tournaments

✍ Scribed by Brian Alspach; K. B. Reid

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 416 KB
Volume: 2
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190020307

No coin nor oath required. For personal study only.

✦ Synopsis

The number of vertices in a digraph G having a particular outdegree (indegree) is called the frequency of the outdegree (indegree). A set f of distinct positive integers {f,, f2,. . . , f n } is the frequency set of the digraph G if every outdegree and indegree occurs with frequency { E F and for each f ; ~f there is a least one outdegree and a t least one indegree with frequency f;. We prove that each nonempty set f of positive integers is the frequency set of some tournament, and we determine the smallest possible order for such a tournament. Similar results for asymmetric digraphs are also given. The results and techniques for frequency sets are used to derive corresponding results for vertex frequency partitions.

📜 SIMILAR VOLUMES

In-Tournament Digraphs

✍ J. Bangjensen; J. Huang; E. Prisner 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 859 KB

Locally semicomplete digraphs: A general

Locally semicomplete digraphs: A generalization of tournaments

✍ Jørgen Bang-Jensen 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 1022 KB

## Abstract In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex __x__ the vertices dominated by __x__ induce a semicomplete digraph and the vertices that dominate __x__

On topological tournaments of order 4 in

On topological tournaments of order 4 in digraphs of outdegree 3

✍ Mader, W. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 371 KB 👁 1 views

It is proved that every finite digraph of minimum outdegree 3 contains a subdivision of the transitive tournament on 4 vertices.

Maximum directed cuts in digraphs with d

Maximum directed cuts in digraphs with degree restriction

✍ Jenö Lehel; Frédéric Maffray; Myriam Preissmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB

## Abstract For integers __m, k__≥1, we investigate the maximum size of a directed cut in directed graphs in which there are __m__ edges and each vertex has either indegree at most __k__ or outdegree at most __k__. © 2009 Wiley Periodicals, Inc. J Graph Theory

Degrees in a digraph whose nodes are gra

Degrees in a digraph whose nodes are graphs

✍ Krystyna T. Balińska; Louis V. Quintas 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 609 KB

Subgraphs and Their Degree Sequences of

Subgraphs and Their Degree Sequences of a Digraph

✍ Wai-Kai Chen 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 912 KB

7'he paper presents general conditions that are necessary and suficient for the existence of a (p, s) subgraph with prescribed degrees of a given digraph. It is shown that the subgraph problem of a digraph, the degree sequence problem of a digraph, the subgraph problem of a graph and the degree sequ