𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An improvement of the Dulmage-Mendelsohn theorem

✍ Scribed by Jian Shen

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
220 KB
Volume
158
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

An n x n nonnegative matrix A is called primitive if for some positive integer k, every entry in the matrix Ak is positive or, in notation, A' + 0. The exponent of primitivity of A is defined to be y(A) = minjk E H, : Ah % 0}, where Z, denotes the set of positive integers. The well known Dulmage-Mendelsohn theorem is that y(A) < n + s(n -2), where s is the shortest circuit in D(A), the directed graph of A. In this paper we prove that y(A) < D + 1 + s(D -l), where D is the diameter of D(A).

πŸ“œ SIMILAR VOLUMES

An improvement of the crossing number bo
An improvement of the crossing number bound
✍ Bernard Montaron πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 194 KB

## Abstract The crossing number __cr__(__G__) of a simple graph __G__ with __n__ vertices and __m__ edges is the minimum number of edge crossings over all drawings of __G__ on the ℝ^2^ plane. The conjecture made by ErdΕ‘s in 1973 that __cr__(__G__) β‰₯ __Cm__^3^/__n__^2^ was proved in 1982 by Leighton

An Improvement of the Boshier-Nomura Bou
An Improvement of the Boshier-Nomura Bound
✍ A. Hiraki πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 93 KB

We show that the number of columns \(\left(c_{i}, a_{i}, b_{i}\right)=(1,1, k-2)\) in the intersection arrays of distance-regular graphs is at most three if the column \((1,0, k-1)\) exists. This improves the Bosheir-Nomura bound from four to three. 1994 Academic Press, Inc.