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 .     

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

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

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 .     

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.     

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

List-edge and list-total colorings of graphs embedded on hyperbolic surfaces

In the paper, we prove that if G is a graph embeddable on a surface of Euler characteristic ε<0 and , then and . This extends a result of Borodin, Kostochka and Woodall [O.V. Borodin, A.V. Kostochka, D.R. Woodall, List-edge and list-total colorings of multigraphs, J. Comb. Theory Series B 71 (1997) 184-204].     

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.     

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.     

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 .     

Equivariant chain complexes, twisted homology and relative minimality of arrangements

We show that the π-equivariant chain complex (), , associated to a Morse-theoretic minimal CW-structure X on the complement of an arrangement , is independent of X. The same holds for all scalar extensions, , a field, where X is an arbitrary minimal CW-structure on a space M. When is a section of another arrangement , we show that the divisibility properties of the first Betti number of the Milnor fiber of  obstruct the homotopy realization of  as a subcomplex of a minimal structure on .If is aspherical and is a sufficiently generic section of , then may be described in terms of π, L and , for an arbitrary local system L; explicit computations may be done, when is fiber-type. In this case, explicit -presentations of arbitrary abelian scalar extensions of the first non-trivial higher homotopy group of , π_p(M), may also be obtained. For nonresonant abelian scalar extensions, the -rank of is combinatorially determined.     

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

Polynomial identities and noncommutative versal torsors

To any cleft Hopf Galois object, i.e., any algebra obtained from a Hopf algebra H by twisting its multiplication with a two-cocycle α, we attach two “universal algebras” and . The algebra is obtained by twisting the multiplication of H with the most general two-cocycle σ formally cohomologous to α. The cocycle σ takes values in the field of rational functions on H. By construction, is a cleft H-Galois extension of a “big” commutative algebra . Any “form” of can be obtained from by a specialization of and vice versa. If the algebra is simple, then is an Azumaya algebra with center . The algebra is constructed using a general theory of polynomial identities that we set up for arbitrary comodule algebras; it is the universal comodule algebra in which all comodule algebra identities of are satisfied. We construct an embedding of into ; this embedding maps the center of into when the algebra is simple. In this case, under an additional assumption, , thus turning into a central localization of . We completely work out these constructions in the case of the four-dimensional Sweedler algebra.     

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.     

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.     

Long alternating paths in bicolored point sets

Given n red and n blue points in convex position in the plane, we show that there exists a noncrossing alternating path of length . We disprove a conjecture of Erd?s by constructing an example without any such path of length greater than .