Abstract. The Caccetta–Häggkvist conjecture (denoted CHC) states that the directed girth (the smallest length of a directed cycle) [Formula: see text] of a directed graph [Formula: see text] on [Formula: see text] vertices is at most [Formula: see text], where [Formula: see text] is the minimum outdegree of [Formula: see text]. We consider a version involving all outdegrees, not merely the minimum one, and prove that if [Formula: see text] does not contain a sink, then [Formula: see text]. In the spirit of a generalization of the CHC to rainbow cycles in [ 1 ], this suggests the conjecture that given nonempty sets [Formula: see text] of edges of [Formula: see text], there exists a rainbow cycle of length at most [Formula: see text]. We prove a bit stronger result when [Formula: see text], thereby strengthening a result of DeVos et al. [ J. Graph Theory, 96 (2021), pp. 192–202]. We prove a logarithmic bound on the rainbow girth in the case that the sets [Formula: see text] are triangles.

We prove that every family of (not necessarily distinct) odd cycles $O_1, \dots, O_{2\lceil n/2 \rceil-1}$ in the complete graph $K_n$ on $n$ vertices has a rainbow odd cycle (that is, a set of edges from distinct $O_i$'s, forming an odd cycle). As part of the proof, we characterize those families of $n$ odd cycles in $K_{n+1}$ that do not have any rainbow odd cycle. We also characterize those families of $n$ cycles in $K_{n+1}$, as well as those of $n$ edge-disjoint nonempty subgraphs of $K_{n+1}$, without any rainbow cycle.

Let $f(n)$ be the smallest number such that every collection of $n$ matchings, each of size at least $f(n)$, in a bipartite graph, has a full rainbow matching. Generalizing famous conjectures of Ryser, Brualdi, and Stein, Aharoni and Berger [ Electron. J. Combin., 16 (2009), R119] conjectured that $f(n)=n+1$ for every $n>1$. Clemens and Ehrenmüller proved that $f(n) \le \frac{3}{2}n +o(n)$. We show that the $o(n)$ term can be reduced to a constant, namely, $f(n) \le \lceil \frac{3}{2}n \rceil+1$.

The Alon--Tarsi Latin squares conjecture is extended to odd dimensions by stating it for reduced Latin squares (Latin squares having the identity permutation as their first row and first column). Using a modified version of an identity proved by Onn [Amer. Math. Monthly, 104 (1997), pp. 156--159], we show that the validity of this conjecture implies a weak version of Rota's bases conjecture for odd dimensions, namely that a set of $n$ bases in $\mathbb{R}^n$ has $n-1$ disjoint independent transversals.

This correspondence examines the Cramer-Rao (CR) bound for data obtained in emission tomography. The likelihood function involved is the combined probability of independent Poisson random variables, the expectation of each being a linear function c/sub i//sup T//spl lambda/ of the parameter vector /spl lambda/. We investigated the achievability of the CR bound in the interior and on the boundary of the domain of the problem. For the former, we found that the CR bound is achievable if and only if the c/sub i/ vectors are obtained from a basis for R/sup N/, by repeating some vectors, multiplied by constant factors. A similar result holds for the boundary case. The practical implication of the achievability condition is that the CR bound is not attainable for typical emission tomographic systems.

Early development of digital topology concentrated on tessellations of the plane into square-shaped pixels, each one of which had a 1 or a 0 assigned to it. It became quickly apparent that in order to avoid some “paradoxes” one needs to consider adjacencies in addition to that provided by the edge-adjacency. The customary choice became the use of a pair of adjacencies; one for the 1-pixels and another for the 0-pixels. While this approach can be treated in a mathematically rigorous fashion, it nevertheless remains attractive to consider those digital spaces in which a single adjacency sufficies to usefully define connectivity. This not only makes the resulting mathematics more elegant, but it also brings the subject nearer to classical graph theory and its enormous wealth of results. This is what motivated us to search for an appropriate new concept. Jordan curves have an interior and an exterior which between them contain all the points not on the curve and both of which are connected, but are disconnected from each other. Generalization to surfaces in digital spaces is useful when displaying (only the exterior of a surface is visible from any direction) or analyzing (the interior volume is well defined). Boundaries in digital spaces may or may not be Jordan, but are “guaranteed” to be Jordan in spaces we call strong Jordan graphs. In this paper we define such a notion of a strong Jordan graph. We show that some previously studied classes (such as those of 1-simply connected digital spaces and of bridged graphs) are subclasses of strong Jordan graphs. We also define Jordan graphs, as those digital spaces in which finite boundaries are guaranteed to be Jordan and show that there are Jordan graphs which are not strong Jordan graphs. (Strong) Jordan graphs are characterized by the existence of “cuts” in associated graphs, by the acyclic nature of the adjacency graphs of binary pictures, and also by the connectedness of the immediate interiors (or exteriors) of certain types of surfaces. The surfaces of the last category include the so-called minimally near-Jordan surfaces, which are shown to be of some interest. Finally, we tie some of these notions to standard notions of graph theory, such as the notion of a separating set. Our overall conclusion is that those digital spaces which are Jordan graphs have some very desirable properties which make their use advantageous whenever the underlying situation allows us to use them.

We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions.