Linkability in iterated line graphs

We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L³(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number k_G such that for every i?k_G the i-iterated line graph of G is -linked. Since the degree of Lⁱ(G) is even, the result is best possible.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Chromatic characterization of biclique covers

A biclique B of a simple graph G is the edge-set of a complete bipartite subgraph of G. A biclique cover of G is a collection of bicliques covering the edge-set of G. Given a graph G, we will study the following problem: find the minimum number of bicliques which cover the edge-set of G. This problem will be called the minimum biclique cover problem (MBC). First, we will define the families of independent and dependent sets of the edge-set E(G) of G: F⊆E(G) will be called independent if there exists a biclique B⊆E(G) such that F⊆B, and will be called dependent otherwise. From our study of minimal dependent sets we will derive a 0-1 linear programming formulation of the following problem: find the maximum weighted biclique in a graph. This formulation may have an exponential number of constraints with respect to the number of nodes of G but we will prove that the continuous relaxation of this integer program can be solved in polynomial time. Finally we will also study continuous relaxation methods for the problem (MBC). This research was motivated by an open problem of Fishburn and Hammer.     

Scalar conservation laws with general boundary condition and continuous flux function

We introduce a notion of entropy solution for a scalar conservation law on a bounded domain with nonhomogeneous boundary condition: ut+divΦ(u)=f on Q=(0,T)×Ω, u(0,⋅)=u₀ on Ω and “u=a on some part of the boundary (0,T)×∂Ω.” Existence and uniqueness of the entropy solution is established for any Φ∈C(R;RN), u₀∈L^∞(Ω), f∈L^∞(Q), a∈L^∞((0,T)×∂Ω). In the L¹-setting, a corresponding result is proved for the more general notion of renormalised entropy solution.     

On the regularity and stability of Pritchard-Salamon systems

Let Σ(S(⋅),B,−) be a Pritchard-Salamon system for (W,V), where W and V are Hilbert spaces. Suppose U is a Hilbert space and F∈L(W,U) is an admissible output operator, SBF(⋅) is the corresponding admissible perturbation C₀-semigroup. We show that the C₀-semigroup SBF(⋅) persists norm continuity, compactness and analyticity of C₀-semigroup S(⋅) on W and V, respectively. We also characterize the compactness and norm continuity of ΔBF(t)=SBF(t)−S(t) for t>0. In particular, we unexpectedly find that ΔBF(t) is norm continuous for t>0 on W and V if the embedding from W into V is compact. Moreover, from this we give some relations between the spectral bounds and growth bounds of SBF(⋅) and S(⋅), so we obtain some new stability results.     

Series representations for some mathematical constants

The authors apply a classical series identity involving the psi (or digamma) function with a view to deriving series representations for a number of known mathematical constants. Several closely-related consequences and results are also considered.     

On the solvable operators generated by uniformly correct problems

A first order differential-operator equation with an operator-coefficient generating a C₀ class semi-group is studied. Boundary conditions for which this equation possesses a unique solution dependent continuously on its right-hand side are derived. Two theorems are formulated and proved.     

Multilinear commutators of Calderón-Zygmund operators on Hardy-type spaces with non-doubling measures

Under the assumption that μ is a non-negative Radon measure on Rd which only satisfies some growth condition, the authors obtain the boundedness in some Hardy-type spaces of multilinear commutators generated by Calderón-Zygmund operators or fractional integrals with RBMO(μ) functions, where the Hardy-type spaces are some appropriate subspaces, associated to the considered RBMO(μ) functions, of the Hardy space H¹(μ) of Tolsa.     

On the integrality of nth roots of generating functions

Motivated by the discovery that the eighth root of the theta series of the E₈ lattice and the 24th root of the theta series of the Leech lattice both have integer coefficients, we investigate the question of when an arbitrary element f∈R (where R=1+xZ?x?) can be written as f=gn for g∈R, n?2. Let Pn:={gn|g∈R} and let . We show among other things that (i) for f∈R, f∈Pn⇔f (mod μn)∈Pn, and (ii) if f∈Pn, there is a unique g∈Pn with coefficients mod μn/n such that f≡gn (mod μn). In particular, if f≡1 (mod μn) then f∈Pn. The latter assertion implies that the theta series of any extremal even unimodular lattice in Rn (e.g. E₈ in R⁸) is in Pn if n is of the form i²j³k⁵ (i?3). There do not seem to be any exact analogues for codes, although we show that the weight enumerator of the rth order Reed-Muller code of length m² is in Pr² (and similarly that the theta series of the Barnes-Wall lattice BWm² is in Pm²). We give a number of other results and conjectures, and establish a conjecture of Paul D. Hanna that there is a unique element f∈Pn (n?2) with coefficients restricted to the set {1,2,…,n}.