Covers in hypergraphs

Let α(H) denote the stability number of a hypergraphH. The covering number ?(H) is defined as the minimal number of edges fromH to cover its vertex setV(H). The main result is the following extension of König’s wellknown theorem: If α(H′)≧|V(H′)|/2 holds for every section hypergraphH′ ofH then ?(H)≦α(H). This theorem is applied to obtain upper bounds on certain covering numbers of graphs and hypergraphs. In par ticular, we prove a conjecture of B. Bollobás involving the hypergraph Turán numbers.     

Vertex Coloring of Graphs by Total 2-Weightings

An assignment of weights to the edges and the vertices of a graph is a vertex-coloring total weighting if adjacent vertices have different total weight sums. Of interest in this paper are vertex-coloring total weightings with weight set of cardinality two, a problem motivated by the conjecture that every graph has such a weighting using the weights 1 and 2. Here we prove the existence of such weightings for certain families of graphs using any two different real weights. A related problem where all vertices have unique weight sums is also discussed.     

Hierarchical matrix techniques for low- and high-frequency Helmholtz problems

Wolfgang Hackbusch ^{In this paper, we discuss the application of hierarchical matrixtechniques to the solution of Helmholtz problems with largewave number in 2D. We consider the Brakhage–Werner integralformulation of the problem discretized by the Galerkin boundary-elementmethod. The dense n x n Galerkin matrix arising from this approachis represented by a sum of an -matrix and an 2-matrix, two different hierarchical matrix formats.A well-known multipole expansion is used to construct the 2-matrix. We present a new approach to dealingwith the numerical instability problems of this expansion: theparts of the matrix that can cause problems are approximatedin a stable way by an -matrix. Algebraic recompression methods are used to reducethe storage and the complexity of arithmetical operations ofthe -matrix.Further, an approximate LU decomposition of such a recompressed-matrix is aneffective preconditioner. We prove that the construction ofthe matrices as well as the matrix-vector product can be performedin almost linear time in the number of unknowns. Numerical experimentsfor scattering problems in 2D are presented, where the linearsystems are solved by a preconditioned iterative method.}     

Synthesis of 5′-deoxy-5′-[18F]fluoro-adenosine by Radiofluorination of 5′-deoxy-5′-haloadenosine Derivatives

5-Deoxy-5-[¹⁸F]fluoro-adenosine was synthesised by nucleophilic radiofluorination reactions of 5-deoxy-5-haloadenosines. The homogeneous isotope exchange in 5-deoxy-5-fluoro-adenosine was also investigated. The conversion of these reactions was found to be rather low and depends on the strength of the halogen-carbon bond: 0.248% for chloride-, 0.488% for bromide- and 1.070% for iodide-derivative; there was no reaction observed in the case of fluoro-compound.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

A panconnectivity theorem for bipartite graphs

Let $G$ be a simple $m\times n$ bipartite graph with $m\ge n$. We prove that if the minimum degree of $G$ satisfies $\delta \left(G\right)\ge m∕2+1$, then $G$ is bipanconnected: for every pair of vertices $x,y$, and for every appropriate integer $2\le ?\le 2n$, there is an $x,y$-path of length $?$ in $G$.     

Locating Pairs of Vertices on a Hamiltonian Cycle in Bigraphs

Let G be a simple \(m\times m\) bipartite graph with minimum degree \(\delta (G)\ge m/2+1\). We prove that for every pair of vertices x, y, there is a Hamiltonian cycle in G such that the distance between x and y along that cycle equals k, where \(2\le k<m/6\) is an integer having appropriate parity. We conjecture that this is also true up to \(k\le m\).