Abstract. Let [Formula: see text] be a multigraph. The cover index [Formula: see text] of [Formula: see text] is the greatest integer [Formula: see text] for which there is a coloring of [Formula: see text] with [Formula: see text] colors such that each vertex of [Formula: see text] is incident with at least one edge of each color. Let [Formula: see text] be the minimum degree of [Formula: see text], and let [Formula: see text] be the codensity of [Formula: see text], defined by [Formula: see text], where [Formula: see text] is the set of all edges of [Formula: see text] with at least one end in [Formula: see text]. It is easy to see that [Formula: see text]. In 1978, Gupta proposed the following codensity conjecture: Every multigraph [Formula: see text] satisfies [Formula: see text], which is the dual version of the Goldberg–Seymour conjecture on edge-colorings of multigraphs. In this note, we prove that [Formula: see text] if [Formula: see text] is not integral and [Formula: see text] otherwise. We also show that this codensity conjecture implies another conjecture concerning the cover index made by Gupta in 1967.

Tutte observed that every nowhere-zero $k$-flow on a plane graph gives rise to a $k$-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer flow and graph coloring can be viewed as dual concepts. Jaeger further shows that if a graph $G$ has a face-$k$-colorable 2-cell embedding in some orientable surface, then it has a nowhere-zero $k$-flow. However, if the surface is nonorientable, then a face-$k$-coloring corresponds to a nowhere-zero $k$-flow in a signed graph arising from $G$. Graphs embedded in orientable surfaces are therefore a special case that the corresponding signs are all positive. In this paper, we prove that if an 8-edge-connected signed graph admits a nowhere-zero integer flow, then it has a nowhere-zero 3-flow. Our result extends Thomassen's 3-flow theorem on 8-edge-connected graphs to the family of all 8-edge-connected signed graphs. And it also improves Zhu's 3-flow theorem on 11-edge-connected signed graphs.

Let $G=(V_1,V_2,E)$ be a balanced bipartite graph with $2n$ vertices. The bipartite binding number of $G$, denoted by $B(G)$, is defined to be $n$ if $G=K_{n,n}$ and $\min_{i\,\in\,\{1,2\}}\,\min_{\emptyset\ne S\subseteq V_i\atop\hfill |N(S)| 3/2$ and $n \ge 139$, then $G$ is bipancyclic; the bound $3/2$ is best possible in the sense that there exist infinitely many balanced bipartite graphs $G$ that have $B(G)=3/2$ but are not Hamiltonian.

Facility location, arising in a rich variety of applications, has been studied extensively in the fields of operations research and computer science. In this paper we consider the classical uncapacitated facility location problem and its “prize-collecting" variant introduced by Baïou and Barahona, and we show that the linear systems associated with these problems are totally dual integral if and only if the input graphs do not contain a certain type of odd cycles. As corollaries, we get structural characterizations of two min-max relations on facility location. Our results strengthen the integrality theorems on facility location polytopes proved by Baïou and Barahona; our proofs lead to combinatorial polynomial-time algorithms for the facility location problems that we consider.

Given a preference system $(G, \prec)$ and an integral weight function defined on the edge set of $G$ (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of $(G, \prec)$ with maximum total weight. In this paper we study this $NP$-hard problem using linear programming and polyhedral approaches. We show that the Rothblum system for defining the fractional stable matching polytope of $(G, \prec)$ is totally dual integral if and only if this polytope is integral if and only if $(G, \prec)$ has a bipartite representation. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system with a bipartite representation. Our results generalize Király and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work.

A graph G is called CIS if each maximal clique intersects each maximal stable set in G and is called almost CIS if it has a unique disjoint pair $(C,S)$ consisting of a maximal clique C and a maximal stable set S. While it is still unknown if there exists a good structural characterization of all CIS graphs, in this note we prove the following Andrade–Boros–Gurvich conjecture: A graph is almost CIS if and only if it is a split graph with a unique split partition.

The following open problem was proposed by Archdeacon: Characterize all graphical sequences $\pi$ such that some realization of $\pi$ admits a nowhere-zero 3-flow. The purpose of this paper is to resolve this problem and present a complete characterization: A graphical sequence $\pi = (d_1,d_2,\dots,d_n)$ with minimum degree at least two has a realization that admits a nowhere-zero 3-flow if and only if $\pi \neq (3^4,2)$, $(k,3^k)$, $(k^2,3^{k-1})$, where k is an odd integer.

We present a structural characterization of all tournaments $T=(V,A)$ such that, for any nonnegative integral weight function defined on V, the maximum size of a feedback vertex set packing is equal to the minimum weight of a triangle in T. We also answer a question of Frank by showing that it is $NP$-complete to decide whether the vertex set of a given tournament can be partitioned into two feedback vertex sets. In addition, we give exact and approximation algorithms for the feedback vertex set packing problem on tournaments.

Jackson and Wormald conjecture that if G is a 3‐connected n‐vertex graph with maximum degree $d\ge 4$, then G has a cycle of length $\Omega(n^{\log_{d-1}2})$. We show that this conjecture holds when $d-1$ is replaced by $\max\{64,4d+1\}$. Our proof implies a cubic algorithm for finding such a cycle.

It is shown by using differential methods that if ${\cal H}$ is a double linear, r-uniform hypergraph with degree sequence $\{d_v\}$ such that any subhypergraph induced by a neighborhood has maximum degree less than m, then its independence number is at least $\sum_{v}f_{r,m}(d_v)$, where $f_{r,m}(x)$ is a convex function satisfying $f_{r,m}(x)\sim (\log x)/x$ if $r=2$ and $c/x^{1/(r-1)}$ if $r \ge 3$, as $x\to\infty$, and $c=c(r,m)>0$ is a constant. The proof yields a polynomial-time algorithm for finding such an independent set in ${\cal H}$.

We consider a problem that arises from communication in all-optical networks. Data are transmitted from source nodes to destination nodes via fixed routes. The high bandwidth of the optic fiber allows for wavelength-division multiplexing so that a single physical optical link can carry several logical signals of different wavelengths. The problem is to carry out a set of requests using a limited number of wavelengths so that different routes using the same wavelength never use the same physical link. We focus on trees of rings which are constructed as follows: Start from a tree and replace each node of the tree by a cycle. Each edge in the tree corresponds to the corresponding cycles sharing a common node. We design an approximation algorithm that routes any set of requests on the tree of rings using no more than 2.5wopt wavelengths, where wopt is the minimum possible number of wavelengths for that set of requests. This improves a 3-approximation solution of Raghavan and Upfal. © 2000 John Wiley & Sons, Inc.

We obtain a necessary and sufficient condition in terms of forbidden structures for tournaments to possess the min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem in this class of tournaments. Applying the local ratio technique of Bar-Yehuda and Even to the forbidden structures, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.

We obtain a necessary and sufficient condition for tournaments to possess a min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem in this class of tournaments; the condition and the algorithms are all based on a totally dual integral (TDI) system, a theoretical framework introduced by J. Edmonds and R. Giles (1994) for establishing min-max results. As a consequence, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.

A file in a distributed database system is replicated on M sites and may contain corrupted pages. Abdel-Ghafiar and El Abbadi gave a detection scheme assuming that the number of corrupted pages f