A contraction of square transversal designs

In this paper we show that if a square transversal design TD_λ[k;u], say D(=(P,B)), admits a class semiregular automorphism group G of order s, then we have a by matrix M with entries from G∪{0} satisfying , where , if i=j, and , otherwise. As an application of (*), we show that any symmetric TD₂[12;6] admits no nontrivial elation. We also obtain a result that gives us a restriction on the existence of elations of putative projective planes of composite order.     

On conjugate adjacency matrices of a graph

Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A^c=[c_ij] is the conjugate adjacency matrix of the graph G if c_ij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and c_ij=0 if i=j. Let P_G(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if P_G(λ)=P_H(λ) and . Further, let P^c(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs G_i=G?i(i=1,2,…,n). If P^c(G)=P^c(H) we prove that , provided that the order of G is greater than 2.     

The cubicity of hypercube graphs

For a graph G, its cubicity is the minimum dimension k such that G is representable as the intersection graph of (axis-parallel) cubes in k-dimensional space. (A k-dimensional cube is a Cartesian product R₁×R₂×?×R_k, where R_i is a closed interval of the form [a_i,a_i+1] on the real line.) Chandran et al. [L.S. Chandran, C. Mannino, G. Oriolo, On the cubicity of certain graphs, Information Processing Letters 94 (2005) 113-118] showed that for a d-dimensional hypercube H_d, . In this paper, we use the probabilistic method to show that . The parameter boxicity generalizes cubicity: the boxicity of a graph G is defined as the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes in k-dimensional space. Since for any graph G, our result implies that . The problem of determining a non-trivial lower bound for is left open.     

Strong convergence of the composite Halpern iteration

Let C be a closed convex subset of a uniformly smooth Banach space E and let T:C→C be a nonexpansive mapping with a nonempty fixed points set. Given a point u∈C, the initial guess x₀∈C is chosen arbitrarily and given sequences , and in (0,1), the following conditions are satisfied:

(i)

;

(ii)

αn→0, βn→0 and 0<a?γn, for some a∈(0,1);

(iii)

, and . Let be a composite iteration process defined by

     

The Cameron-Erd?s conjecture

A subset A of integers is said to be sum-free if a+b∉A for any a,b∈A. Let s(n) be the number of sum-free sets in interval [1,n] of integers. P. Cameron and P. Erd?s conjectured that s(n)=O(2^n/2). We show that for even n and for odd n, where are absolute constants, thereby proving the conjecture.     

Combinatorial sums and finite differences

We present a new approach to evaluating combinatorial sums by using finite differences. Let and be sequences with the property that Δb_k=a_k for k?0. Let , and let . We derive expressions for g_n in terms of h_n and for h_n in terms of g_n. We then extend our approach to handle binomial sums of the form , , and , as well as sums involving unsigned and signed Stirling numbers of the first kind, and . For each type of sum we illustrate our methods by deriving an expression for the power sum, with a_k=k^m, and the harmonic number sum, with a_k=H_k=1+1/2+?+1/k. Then we generalize our approach to a class of numbers satisfying a particular type of recurrence relation. This class includes the binomial coefficients and the unsigned Stirling numbers of the first kind.     

Total domination and total domination subdivision number of a graph and its complement

A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγ_t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersd_γt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n?4, minimum degree δ and maximum degree Δ. We prove that if each component of G and has order at least 3 and , then and if each component of G and has order at least 2 and at least one component of G and has order at least 3, then . We also give a result on stronger than a conjecture by Harary and Haynes.     

Edges not contained in triangles and the number of contractible edges in a 4-connected graph

Let G be a 4-connected graph, and let E_c(G) denote the set of 4-contractible edges of G and let denote the set of those edges of G which are not contained in a triangle. Under this notation, we show that if , then we have .     

Distance irredundance and connected domination numbers of a graph

Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γ_k(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number ir_k(G). The authors prove that if an ir_k-set X is a k-independent set of G, then , and that for k?2, if ir_k(G)=1, if ir_k(G) is odd, and if ir_k(G) is even, which generalize some known results.     

Regularity theorems for parabolic equations

We study regularity properties of solutions of a parabolic equation in R₊×R^d, d?3 under fairly general conditions on the drift term coefficients. The results are already new for the case a=I, , b=b(x) and .     

The subconstituent algebra of a bipartite distance-regular graph; thin modules with endpoint two

We consider a bipartite distance-regular graph Γ with diameter D?4, valency k?3, intersection numbers b_i,c_i, distance matrices A_i, and eigenvalues θ₀>θ₁>?>θ_D. Let X denote the vertex set of Γ and fix x∈X. Let T=T(x) denote the subalgebra of Mat_X(C) generated by , where A=A₁ and denotes the projection onto the ith subconstituent of Γ with respect to x. T is called the subconstituent algebra (or Terwilliger algebra) of Γ with respect to x. An irreducible T-module W is said to be thin whenever for 0?i?D. By the endpoint of W we mean . Assume W is thin with endpoint 2. Observe is a one-dimensional eigenspace for ; let η denote the corresponding eigenvalue. It is known where , and d=⌊D/2⌋. To describe the structure of W we distinguish four cases: (i) ; (ii) D is odd and ; (iii) D is even and ; (iv) . We investigated cases (i), (ii) in MacLean and Terwilliger [Taut distance-regular graphs and the subconstituent algebra, Discrete Math. 306 (2006) 1694-1721]. Here we investigate cases (iii), (iv) and obtain the following results. We show the dimension of W is D-1-e where e=1 in case (iii) and e=0 in case (iv). Let v denote a nonzero vector in . We show W has a basis , where E_i denotes the primitive idempotent of A associated with θ_i and where the set S is {1,2,…,d-1}∪{d+1,d+2,…,D-1} in case (iii) and {1,2,…,D-1} in case (iv). We show this basis is orthogonal (with respect to the Hermitian dot product) and we compute the square-norm of each basis vector. We show W has a basis , and we find the matrix representing A with respect to this basis. We show this basis is orthogonal and we compute the square-norm of each basis vector. We find the transition matrix relating our two bases for W.     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .     

On edge domination numbers of graphs

Let and be the signed edge domination number and signed star domination number of G, respectively. We prove that holds for all graphs G without isolated vertices, where n=|V(G)|?4 and m=|E(G)|, and pose some problems and conjectures.     

On the dimension of trees

We consider isometric embedding of trees into the infinite graph Z_m whose vertices are the m-dimensional lattice points where two vertices a=(a₁,a₂,…,a_m) and b=(b₁,b₂,…,b_m) are adjacent if and only if |a_i-b_i|?1 for 1?i?m. Linial, London, and Rabinovich have shown that this can be done with , where t is the number of leaves. In this note, we sketch a proof that .     

Coloring the complements of intersection graphs of geometric figures

Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rⁿ. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rⁿ.     

A new majorization between functions, polynomials, and operator inequalities

Let P₊ be the set of all non-negative operator monotone functions defined on [0,∞), and put . Then and . For a function and a strictly increasing function h we write if is operator monotone. If and and if and , then . We will apply this result to polynomials and operator inequalities. Let and be non-increasing sequences, and put for t≧a₁ and for t≧b₁. Then v₊?u₊ if m≦n and : in particular, for a sequence of orthonormal polynomials, (p_n-1)₊?(p_n)₊. Suppose 0<r,p and s=0 or 1≦s≦1+p/r. Then 0≦A≦B implies for 0<α≦r/(p+r).     

Quasi sure analysis of local times of anticipating smooth semimartingales

Let be the anticipating smooth semimartingale and be its generalized local time. In this paper, we give some estimates about the quasi sure property of Xt and its quadratic variation process t〈X〉. We also study the fractional smoothness of and prove that the quadratic variation process of can be constructed as the quasi sure limit of the form , where is a sequence of subdivisions of [a,b], , i=0,1,…,n².