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.     

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.     

Nomadic decompositions of bidirected complete graphs

We use to denote the bidirected complete graph on n vertices. A nomadic Hamiltonian decomposition of is a Hamiltonian decomposition, with the additional property that “nomads” walk along the Hamiltonian cycles (moving one vertex per time step) without colliding. A nomadic near-Hamiltonian decomposition is defined similarly, except that the cycles in the decomposition have length n-1, rather than length n. Bondy asked whether these decompositions of exist for all n. We show that admits a nomadic near-Hamiltonian decomposition when .     

A note on maximality of analytic crossed products

Let G be a compact abelian group with the totally ordered dual group which admits the positive semigroup . Let N be a von Neumann algebra and be an automorphism group of on N. We denote to the analytic crossed product determined by N and α. We show that if is a maximal σ-weakly closed subalgebra of , then induces an archimedean order in .     

On the number of graphs with a given endomorphism monoid

For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .     

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 Farahat-Higman ring of wreath products and Hilbert schemes

We study the structure constants of the class algebra of the wreath products Γ_n associated to an arbitrary finite group Γ with respect to the basis of conjugacy classes. We show that a suitable filtration on gives rise to the graded ring with non-negative integer structure constants independent of n (some of which are computed), which are then encoded in a Farahat-Higman ring . The real conjugacy classes of Γ come to play a distinguished role and are treated in detail in the case when Γ is a subgroup of . The above results provide new insight to the cohomology rings of Hilbert schemes of points on a quasi-projective surface X.     

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).     

Classification of quasifinite modules over the Lie algebras of Weyl type

For a nondegenerate additive subgroup Γ of the n-dimensional vector space over an algebraically closed field of characteristic zero, there is an associative algebra and a Lie algebra of Weyl type spanned by all differential operators uD₁^m₁?D_n^m_n for (the group algebra), and m₁,…,m_n?0, where D₁,…,D_n are degree operators. In this paper, it is proved that an irreducible quasifinite -module is either a highest or lowest weight module or else a module of the intermediate series; furthermore, a classification of uniformly bounded -modules is completely given. It is also proved that an irreducible quasifinite -module is a module of the intermediate series and a complete classification of quasifinite -modules is also given, if Γ is not isomorphic to .     

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.     

On sums of binomial coefficients and their applications

In this paper we study recurrences concerning the combinatorial sum and the alternate sum , where m>0, n?0 and r are integers. For example, we show that if n?m-1 then

     

The zero-divisor graph of a reduced ring

In this paper the zero-divisor graph Γ(R) of a commutative reduced ring R is studied. We associate the ring properties of R, the graph properties of Γ(R) and the topological properties of . Cycles in Γ(R) are investigated and an algebraic and a topological characterization is given for the graph Γ(R) to be triangulated or hypertriangulated. We show that the clique number of Γ(R), the cellularity of and the Goldie dimension of R coincide. We prove that when R has the annihilator condition and ; Γ(R) is complemented if and only if is compact. In a semiprimitive Gelfand ring, it turns out that the dominating number of Γ(R) is between the density and the weight of . We show that Γ(R) is not triangulated and the set of centers of Γ(R) is a dominating set if and only if the set of isolated points of is dense in .     

Posets of annular non-crossing partitions of types B and D

We study the set of annular non-crossing permutations of type B, and we introduce a corresponding set of annular non-crossing partitions of type B, where p and q are two positive integers. We prove that the natural bijection between and is a poset isomorphism, where the partial order on is induced from the hyperoctahedral group B_p+q, while is partially ordered by reverse refinement. In the case when q=1, we prove that is a lattice with respect to reverse refinement order.We point out that an analogous development can be pursued in type D, where one gets a canonical isomorphism between and . For q=1, the poset coincides with a poset “NC^(D)(p+1)” constructed in a paper by Athanasiadis and Reiner [C.A. Athanasiadis, V. Reiner, Noncrossing partitions for the group D_n, SIAM Journal of Discrete Mathematics 18 (2004) 397-417], and is a lattice by the results of that paper.     

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 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.     

Compactness via symmetrization

Consider two types of translation-invariant functionals and on , and a sequence of functions f_n whose corresponding symmetric rearrangements are convergent. We show that f_n themselves converge up to translations if either or . These compactness results lead to applications in variational problems and stability problems in stellar dynamics.     

Quartic residues and binary quadratic forms

Let be a prime, m∈Z and . In this paper we obtain a general criterion for m to be a quartic residue in terms of appropriate binary quadratic forms. Let d>1 be a squarefree integer such that , where is the Legendre symbol, and let ε_d be the fundamental unit of the quadratic field . Since 1942 many mathematicians tried to characterize those primes p so that ε_d is a quadratic or quartic residue . In this paper we will completely solve these open problems by determining the value of , where p is an odd prime, and . As an application we also obtain a general criterion for , where {u_n(a,b)} is the Lucas sequence defined by and .