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

     

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.     

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.     

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 .     

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

Edge-recognizable domination numbers

For any undirected graph G, let be the collection of edge-deleted subgraphs. It is always possible to construct a graph H from so that . The general edge-reconstruction conjecture states that G and H must be isomorphic if they have at least four edges. A graphical invariant that must be identical for all graphs that can be constructed from the given collection is said to be edge-recognizable. Here we show that the domination number and many of its common variations are edge-recognizable.     

On NP-hardness of the clique partition—Independence number gap recognition and related problems

We show that for a graph G it is NP-hard to decide whether its independence number α(G) equals its clique partition number even when some minimum clique partition of G is given. This implies that any α(G)-upper bound provably better than is NP-hard to compute.To establish this result we use a reduction of the quasigroup completion problem (QCP, known to be NP-complete) to the maximum independent set problem. A QCP instance is satisfiable if and only if the independence number α(G) of the graph obtained within the reduction is equal to the number of holes h in the QCP instance. At the same time, the inequality always holds. Thus, QCP is satisfiable if and only if . Computing the Lovász number ?(G) we can detect QCP unsatisfiability at least when . In the other cases QCP reduces to gap recognition, with one minimum clique partition of G known.     

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.     

Edge covered critical multigraphs

Let G be a multigraph with edge set E(G). An edge coloring C of G is called an edge covered coloring, if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k edge covered coloring is called the edge covered chromatic index of G and is denoted by . A graph G is said to be of class if and otherwise of class. A pair of vertices {u,v} is said to be critical if . A graph G is said to be edge covered critical if it is of class and every edge with vertices in V(G) not belonging to E(G) is critical. Some properties about edge covered critical graphs are considered.     

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.     

On powers of the Heaviside function for negative integers

The distributions and were defined as the neutrix limit of the sequences and respectively for , see [J.D. Nicholos, B. Fisher, The distribution composition , J. Math. Anal. Appl. 258 (2001) 131-145; B. Fisher, On defining the distribution , Univ. u Novom Sadu Zb. Rad. Prirod. Mat. Fak. Ser. Mat. 15 (1985) 119-129]. We here consider these distributions when r=0. In other words, we define the sth powers of the Heaviside function H(x) in the distributional sense for negative integers. Further compositions are also considered.     

On wreathed lexicographic products of graphs

This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G.     

Lattices generated by join of strongly closed subgraphs in d-bounded distance-regular graphs

Let Γ be a d-bounded distance-regular graph with diameter d?3. Suppose that P(x) is a set of all strongly closed subgraphs containing x and that P(x,i) is a subset of P(x) consisting of all elements of P(x) with diameter i. Let L^′(x,i) be the set generated by all joins of the elements in P(x,i). By ordering L^′(x,i) by inclusion or reverse inclusion, L^′(x,i) is denoted by or . We prove that and are both finite atomic lattices, and give the conditions for them both being geometric lattices. We also give the eigenpolynomial of      

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 .     

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.     

Hamilton decompositions of directed cubes and products

Call a directed graph symmetric if it is obtained from an undirected graph G by replacing each edge of G by two directed edges, one in each direction. We will show that if G has a Hamilton decomposition with certain additional structure, then has a directed Hamilton decomposition. In particular, it will follow that the bidirected cubes for m?2 are decomposable into 2m+1 directed Hamilton cycles and that a product of cycles is decomposable into 2m+1 directed Hamilton cycles if n_i?3 and m?2.     

On the Laplacian spectral radii of trees

Let Δ(T) and μ(T) denote the maximum degree and the Laplacian spectral radius of a tree T, respectively. Let T_n be the set of trees on n vertices, and . In this paper, we determine the two trees which take the first two largest values of μ(T) of the trees T in when . And among the trees in , the tree which alone minimizes the Laplacian spectral radius is characterized. We also prove that for two trees T₁ and T₂ in , if Δ(T₁)>Δ(T₂) and , then μ(T₁)>μ(T₂). As an application of these results, we give a general approach about extending the known ordering of trees in T_n by their Laplacian spectral radii.