𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Greene-Kleitman's theorem for general digraphs

✍ Scribed by Ron Aharoni; Irith Ben-Arroyo Hartman

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
706 KB
Volume
120
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 Greene and Frank to acyclic digraphs.

πŸ“œ SIMILAR VOLUMES

On greene's theorem for digraphs
On greene's theorem for digraphs
✍ Irith Ben-Arroyo Hartman; Fathi Saleh; Daniel Hershkowitz πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 328 KB

## Abstract Greene's Theorem states that the maximum cardinality of an optimal __k__‐path in a poset is equal to the minimum __k__‐norm of a __k__‐optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general dig

A generalized Green's theorem
A generalized Green's theorem
✍ Dongwoo Sheen πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 316 KB

## Abztract- The generalized Green's theorem introduced in [l] for smooth domains is here extended to Lipschitz domahrs (hence, including the case of polyhedrons, which is particularly important in numerical analysis). For first-order linear differential systems whose coefficient matrices are Lipc

Meyniel's theorem for strongly (p, q) -
Meyniel's theorem for strongly (p, q) - Hamiltonian digraphs
✍ A. P. Wojda πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 134 KB

## Abstract We give the following theorem: Let __D__ = (__V, E__) be a strongly (__p__ + __q__ + 1)‐connected digraph with __n__ β‰₯ __p__ + __q__ + 1 vertices, where __p__ and __q__ are nonnegative integers, __p__ ≀ __n__ ‐ 2, __n__ β‰₯ 2. Suppose that, for each four vertices __u, v, w, z__ (not neces

On a generalization of transitivity for
On a generalization of transitivity for digraphs
✍ Andras GyΓ‘rfΓ‘s; Michael S. Jacobson; Lael F. Kinch πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 758 KB

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

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