On strong unimodality of multivariate discrete distributions

A discrete function f defined on Zⁿ is said to be logconcave if for , , . A more restrictive notion is strong unimodality. Following Barndorff-Nielsen [O. Barndorff-Nielsen, Unimodality and exponential families, Commun. Statist. 1 (1973) 189-216] a discrete function is called strongly unimodal if there exists a convex function such that  if . In this paper sufficient conditions that ensure the strong unimodality of a multivariate discrete distribution, are given. Examples of strongly unimodal multivariate discrete distributions are presented.     

On the asymptotic number of inequivalent binary self-dual codes

Let Ψn be the number of inequivalent self-dual codes in . We prove that , where . Let Δn be the number of inequivalent doubly even self-dual codes in . We also prove that .     

On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2

We improve parts of the results of [T. W. Cusick, P. Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Mathematics 258 (2002) 289-301; J. Pieprzyk, C. X. Qu, Fast hashing and rotation-symmetric functions, Journal of Universal Computer Science 5 (1) (1999) 20-31]. It is observed that the n-variable quadratic Boolean functions, for , which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weights and nonlinearity are exactly characterized by the cyclic subgroup 〈s−1〉 of Z_n. If , the order of s−1, is even, the weight and nonlinearity are the same and given by . If the order is odd, it is balanced and nonlinearity is given by .     

The connectivity of a graph and its complement

Let G be a graph with minimum degree δ(G), edge-connectivity λ(G), vertex-connectivity κ(G), and let be the complement of G.In this article we prove that either λ(G)=δ(G) or . In addition, we present the Nordhaus-Gaddum type result . A family of examples will show that this inequality is best possible.     

On a conjecture of Erd?s, Graham and Spencer, II

It is conjectured by Erd?s, Graham and Spencer that if 1≤a₁≤a₂≤?≤a_s are integers with , then this sum can be decomposed into n parts so that all partial sums are ≤1. This is not true for as shown by a₁=?=a_n−2=1, . In 1997 Sandor proved that Erd?s-Graham-Spencer conjecture is true for . Recently, Chen proved that the conjecture is true for . In this paper, we prove that Erd?s-Graham-Spencer conjecture is true for .     

Forwarding and optical indices of a graph

Motivated by wavelength-assignment problems for all-to-all traffic in optical networks, we study graph parameters related to sets of paths connecting all pairs of vertices. We consider sets of both undirected and directed paths, under minimisation criteria known as edge congestion and wavelength count; this gives rise to four parameters of a graph G: its edge forwarding index π(G), arc forwarding index , undirected optical index , and directed optical index .In the paper we address two long-standing open problems: whether the equality holds for all graphs, and whether indices π(G) and are hard to compute. For the first problem, we give an example of a family of planar graphs {G_k} such that . For the second problem, we show that determining either π(G) or is NP-hard.     

Two classes of edge domination in graphs

Let (, resp.) be the number of (local) signed edge domination of a graph G [B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189]. In this paper, we prove mainly that and hold for any graph G of order n(n?4), and pose several open problems and conjectures.     

Cyclic bandwidth with an edge added

B_c(G) denotes the cyclic bandwidth of graph G. In this paper, we obtain the maximum cyclic bandwidth of graphs of order p with adding an edge as follows:

     

Connectivity preserving transformations for higher dimensional binary images

An N-dimensional digital binary image (I) is a function I:Z^N→{0,1}. I is connected if and only if its black pixels and white pixels are each (3^N−1)-connected. I is only connected if and only if its black pixels are (3^N−1)-connected. For a 3-D binary image, the respective connectivity models are and . A pair of (3^N−1)-neighboring opposite-valued pixels is called interchangeable in a N-D binary image I, if reversing their values preserves the original connectedness. We call such an interchange to be a (3^N−1)-local interchange. Under the above connectivity models, we show that given two binary images of n pixels/voxels each, we can transform one to the other using a sequence of (3^N−1)-local interchanges. The specific results are as follows. Any two -connected 3-dimensional images I and J each having n black voxels are transformable using a sequence of O((c₁+c₂)n²) 26-local interchanges. Here, c₁ and c₂ are the total number of 8-connected components in all 2-dimensional layers of I and J respectively. We also show bounds on connectivity under a different interchange model as proposed in [A. Dumitrescu, J. Pach, Pushing squares around, Graphs and Combinatorics 22 (1) (2006) 37-50]. Next, we show that any two simply connected images under the , connectivity model and each having n black voxels are transformable using a sequence of O(n²) 26-local interchanges. We generalize this result to show that any two , -connected N-dimensional simply connected images each having n black pixels are transformable using a sequence of O(Nn²)(3^N−1)-local interchanges, where N>1.     

Exponentiable monomorphisms in categories of domains

We give a characterization of exponentiable monomorphisms in the categories of ω-complete posets, of directed complete posets and of continuous directed complete posets as those monotone maps f that are convex and that lift an element (and then a queue) of any directed set (ω-chain in the case of ) whose supremum is in the image of f (Theorem 1.9). Using this characterization, we obtain that a monomorphism f:X→B in (, ) exponentiable in w.r.t. the Scott topology is exponentiable also in (, ). We prove that the converse is true in the category , but neither in , nor in .     

Minimal arithmetic thickness connecting discrete planes

While connected arithmetic discrete lines are entirely characterized, only partial results exist for the more general case of arithmetic discrete hyperplanes. In the present paper, we focus on the three-dimensional case, that is on arithmetic discrete planes. Thanks to arithmetic reductions on a vector , we provide algorithms either to determine whether a given arithmetic discrete plane with as normal vector is connected, or to compute the minimal thickness for which an arithmetic discrete plane with normal vector is connected.     

Inducing regulation of any digraphs

For a given structure D (digraph, multidigraph, or pseudodigraph) and an integer r large enough, a smallest inducing r-regularization of D is constructed. This regularization is an r-regular superstructure of the smallest possible order with bounded arc multiplicity, and containing D as an induced substructure. The sharp upper bound on the number, ρ, of necessary new vertices among such superstructures for n-vertex general digraphs D is determined, ρ being called the inducing regulation number of D. For being the maximum among semi-degrees in D, simple n-vertex digraphs D with largest possible ρ are characterized if either or (where the case is not a trivial subcase of ).