𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a generalization of transitivity for digraphs

✍ Scribed by Andras Gyárfás; Michael S. Jacobson; Lael F. Kinch

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
758 KB
Volume
69
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we investigate the foliowing generalization of transitivity: A digraph D is (m, n)-transitive whenever there is a path of length m from x to y there is a subset of n + 1 vertices of these m + 1 vertices which contain a path of length n from x to y.

Here we study various properties of (m, n)-transitive digraphs. In particular, (m, I)-transitive tournaments are characterized. Their similarities to transitive tournaments are analyzed and discussed.

Various other results pertaining to (m, I)-transitive digraphs are given.

📜 SIMILAR VOLUMES

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 Greene-Kleitman's theorem for general
On Greene-Kleitman's theorem for general digraphs
✍ Ron Aharoni; Irith Ben-Arroyo Hartman 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 706 KB

Linial conjectured that Greene-Kleitman's theorem can be extended to general digraphs. We prove a stronger conjecture of Berge for digraphs having k-optimal path partitions consisting of 'long' paths. The same method yields known results for acyclic digraphs, and extensions of various theorems of Gr

On labeled vertex-transitive digraphs wi
On labeled vertex-transitive digraphs with a prime number of vertices
✍ Chong-Yun Chao; Jacqueline G. Wells 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 481 KB

## We enumerate, up to isomorphism, several classes of labeled vertex-transitive digraphs with a prime number of vertices. There are many unsolvedi enumeration problems stated in [S]. Recently, Robinson in [8] posed more enumeration problems. Here, we give some partial answer to the problems posed

A class of self-complementary vertex-tra
A class of self-complementary vertex-transitive digraphs
✍ Gek-Ling Chia; Chong-Keang Lim 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB

We characterize the class of self-complementary vertex-transitive digraphs on a prime number p of vertices. Using this, we enumerate (i) self-complementary strongly vertex-transitive digraphs on p vertices, (ii) self-complementary vertex-transitive digraphs on p vertices, (iii) selfcomplementary ver

Cycles through Large Degree Vertices in
Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem
✍ Kenneth A. Berman; Xin Liu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every