Relating broadcast independence and independence

An independent broadcast on a connected graph $G$ is a function $f:V\left(G\right)\to {\mathbb{N}}_0$ such that, for every vertex $x$ of $G$, the value $f\left(x\right)$ is at most the eccentricity of $x$ in $G$, and $f\left(x\right)>0$ implies that $f\left(y\right)=0$ for every vertex $y$ of $G$ within distance at most $f\left(x\right)$ from $x$. The broadcast independence number ${\alpha }_b\left(G\right)$ of $G$ is the largest weight $\sum _{x\in V\left(G\right)}f\left(x\right)$ of an independent broadcast $f$ on $G$. Clearly, ${\alpha }_b\left(G\right)$ is at least the independence number $\alpha \left(G\right)$ for every connected graph $G$. Our main result implies ${\alpha }_b\left(G\right)\le 4\alpha \left(G\right)$. We prove a tight inequality and characterize all extremal graphs.     

Unit and single point interval graphs

We describe a linear time algorithm for the recognition of graphs that have an intersection representation using unit length intervals and single point intervals. Furthermore, we characterize these graphs using forbidden induced subgraphs.     

Das Fließverhalten dispers-plastischer Massen im Walzspalt,untersucht am Beispiel von Kreide-Wasser-Systemen

Zusammenfassung Der Fließvorgang dispers-plastischer Massen im Walzspalt ist mit Hilfe der bisher bekannten Walztheorien nicht zu beschreiben. Die für ingenieurmäßige Rechnungen notwendigen Unterlagen lassen sich jedoch für vorgegebene Stoffe durch Modellversuche schnell ermitteln. Die Versuche bestätigten die ähnlichkeitstheoretische Überlegung, daß Lagerdruck und Antriebsleistung entscheidend durch die dimensionslose Kenngrößeh _o /R beeinflußt werden.     

A note on the least number of edges of 3-uniform hypergraphs with upper chromatic number 2

The upper chromatic number of a hypergraph H=(X,E) is the maximum number k for which there exists a partition of X into non-empty subsets X=X₁∪X₂∪?∪X_k such that for each edge at least two vertices lie in one of the partite sets. We prove that for every n?3 there exists a 3-uniform hypergraph with n vertices, upper chromatic number 2 and ⌈n(n-2)/3⌉ edges which implies that a corresponding bound proved in [K. Diao, P. Zhao, H. Zhou, About the upper chromatic number of a co-hypergraph, Discrete Math. 220 (2000) 67-73] is best-possible.     

On the behaviour of asymmetric membranes in pervaporation

Symmetric and asymmetric membranes of the Loeb type are compared with respect to their performance in pervaporation. The experiments are carried out with water—isopropanol mixtures, employing cellulose acetate membranes of different structure, but of the same total thickness. These results are compared with calculations based on a 2-layer model for asymmetric membranes. Design criteria for optimal asymmetric membranes for pervaporation, as well as the performance characteristics for the two possible modes of installation — active layer facing the feed or facing the permeate — are discussed. Contrary to reverse osmosis, the installation of the membrane with the active layer facing the permeate proves to be superior — at least for low permeabilities of the membrane material. The interdependencies between thickness and permeability of the active layer, and porosity and thickness of the support layer are much stronger than in reverse osmosis.     

Remarks about disjoint dominating sets

We prove several structural and hardness results concerning pairs of disjoint sets in graphs which are dominating or independent and dominating.     

The delay of circuits whose inputs have specified arrival times

Let C be a circuit representing a straight-line program on n inputs x₁,x₂,…,x_n. If for 1?i?n an arrival timet_i∈N₀ for x_i is given, we define the delay of x_i in C as the sum of t_i and the maximum number of gates on a directed path in C starting in x_i. The delay of C is defined as the maximum delay of one of its inputs.The notion of delay is a natural generalization of the notion of depth. It is of practical interest because it corresponds exactly to the static timing analysis used throughout the industry for the analysis of the timing behaviour of a chip. We prove a lower bound on the delay and construct circuits of close-to-optimal delay for several classes of functions. We describe circuits solving the prefix problem on n inputs that are of essentially optimal delay and of size O(nlog(logn)). Finally, we relate delay to formula size.     

Antimalarial activity of plant metabolites

This review covers the structures of compounds with antiplasmodial activity isolated from plants and is organized according to plant family. A total of 170 structures has been reviewed from 186 references found in the literature up to December 2000.     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.