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 .     

Maximum uniformly resolvable designs with block sizes 2 and 4

A central question in design theory dating from Kirkman in 1850 has been the existence of resolvable block designs. In this paper we will concentrate on the case when the block size k=4. The necessary condition for a resolvable design to exist when k=4 is that v≡4mod12; this was proven sufficient in 1972 by Hanani, Ray-Chaudhuri and Wilson [H. Hanani, D.K. Ray-Chaudhuri, R.M. Wilson, On resolvable designs, Discrete Math. 3 (1972) 343-357]. A resolvable pairwise balanced design with each parallel class consisting of blocks which are all of the same size is called a uniformly resolvable design, a URD. The necessary condition for the existence of a URD with block sizes 2 and 4 is that v≡0mod4. Obviously in a URD with blocks of size 2 and 4 one wishes to have the maximum number of resolution classes of blocks of size 4; these designs are called maximum uniformly resolvable designs or MURDs. So the question of the existence of a MURD on v points has been solved for by the result of Hanani, Ray-Chaudhuri and Wilson cited above. In the case this problem has essentially been solved with a handful of exceptions (see [G. Ge, A.C.H. Ling, Asymptotic results on the existence of 4-RGDDs and uniform 5-GDDs, J. Combin. Des. 13 (2005) 222-237]). In this paper we consider the case when and prove that a exists for all u≥2 with the possible exception of u∈{2,7,9,10,11,13,14,17,19,22,31,34,38,43,46,47,82}.     

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.     

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.     

Uniformly resolvable designs with index one and block sizes three and four — with three or five parallel classes of block size four

Each parallel class of a uniformly resolvable design (URD) contains blocks of only one block size. A URD with v points and with block sizes three and four means that at least one parallel class has block size three and at least one has block size four. Danziger [P. Danziger, Uniform restricted resolvable designs with r=3, ARS Combin. 46 (1997) 161-176] proved that for all there exist URDs with index one, some parallel classes of block size three, and exactly three parallel classes with block size four, except when v=12 and except possibly when . We extend Danziger’s work by showing that there exists a URD with index one, some parallel classes with block size three, and exactly three parallel classes with block size four if, and only if, , v≠12. We also prove that there exists a URD with index one, some parallel classes of block size three, and exactly five parallel classes with block size four if, and only if, , v≠12. New labeled URDs, which give new URDs as ingredient designs for recursive constructions, are the key in the proofs. Some ingredient URDs are also constructed with difference families.     

Directed 3-cycle decompositions of complete directed graphs with quadratic leaves

Let G be a vertex-disjoint union of directed cycles in the complete directed graph D_t, let |E(G)| be the number of directed edges of G and suppose or if t=5, and if t=6. It is proved in this paper that for each positive integer t, there exist -decompositions for D_t−G if and only if .     

How to play the Majority game with a liar

The Majority game is played by a questioner () and an answerer (). holds n elements, each of which can be labeled as 0 or 1. is trying to identify some element holds as having the Majority label or, in the case of a tie, claim there is none. To do this asks questions comparing whether two elements have the same or different label. ’s goal is to ask as few questions as possible while ’s goal is to delay as much as possible. Let q^∗ denote the minimal number of questions needed for to identify a Majority element regardless of ’s answers.In this paper we investigate upper and lower bounds for q^∗ in a variation of the Majority game, where is allowed to lie up to t times. We consider two versions of the game, the adaptive (where questions are asked sequentially) and the oblivious (where questions are asked in one batch).     

Maximum bipartite subgraphs of cubic triangle-free planar graphs

Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .     

Lifting Bailey pairs to WP-Bailey pairs

A pair of sequences such that and

     

On cyclic semi-regular subgroups of certain 2-transitive permutation groups

We determine the cyclic semi-regular subgroups of the 2-transitive permutation groups and with n a suitable power of a prime number p.     

Generalization of transitive fraternal augmentations for directed graphs and its applications

Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,

1.

if and then or (fraternity);

2.

if and then (transitivity).

In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col₂(G)≤O(∇₁(G)∇₀(G)²), where ∇_k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇_k(G) bounds the distance (k+1)-coloring number col_k+1(G) with a function f(∇_k(G)). On the other hand, ∇_k(G)≤(col_2k+1(G))^2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.     

Some relations between rank, chromatic number and energy of graphs

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. Let G be a graph of order n and be the rank of the adjacency matrix of G. In this paper we characterize all graphs with . Among other results we show that apart from a few families of graphs, , where n is the number of vertices of G, and χ(G) are the complement and the chromatic number of G, respectively. Moreover some new lower bounds for E(G) in terms of are given.     

Large monochromatic components in colorings of complete 3-uniform hypergraphs

Let f(n,r) be the largest integer m with the following property: if the edges of the complete 3-uniform hypergraph are colored with r colors then there is a monochromatic component with at least m vertices. Here we show that and . Both results are sharp under suitable divisibility conditions (namely if n is divisible by 7, or by 6 respectively).     

A tripling construction for overlarge sets of KTS

An overlarge set of , denoted by , is a collection {(X?{x},B_x):x∈X}, where X is a (v+1)-set, each (X?{x},B_x) is a and {B_x:x∈X} forms a partition of all triples on X. In this paper, we give a tripling construction for overlarge sets of KTS. Our main result is that: If there exists an with a special property, then there exists an . It is obtained that there exists an for u=2²ⁿ⁻¹−1 or u=qⁿ, where prime power q≡7 (mod 12) and m≥0,n≥1.     

Sequences of integers with missing quotients

Let S be any set of natural numbers, and A be a given set of rational numbers. We say that S is an A-quotient-free set if x,y∈S implies y/x∉A. Let and , where the supremum is taken over all A-quotient-free sets S, and are the upper and lower asymptotic densities of S respectively. Let ρ(A)=sup_Sδ(S), where the supremum is taken over all A-quotient-free sets S such that δ(S) exists. In this paper we study the properties of , and ρ(A).     

On (d,1)-total numbers of graphs

A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs K_m,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.     

On the relation between cluster and classical tilting

Let be a triangulated category with a cluster tilting subcategory U. The quotient category is abelian; suppose that it has finite global dimension.We show that projection from to sends cluster tilting subcategories of to support tilting subcategories of , and that, in turn, support tilting subcategories of can be lifted uniquely to weak cluster tilting subcategories of .     

Higher Kurtz randomness

A real x is -Kurtz random (-Kurtz random) if it is in no closed null set ( set). We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.     

On the Wiener integral with respect to a sub-fractional Brownian motion on an interval

The domain of the Wiener integral with respect to a sub-fractional Brownian motion , , k≠0, is characterized. The set is a Hilbert space which contains the class of elementary functions as a dense subset. If , any element of is a function and if , the domain is a space of distributions.     

On the signed edge domination number of graphs

Let be the signed edge domination number of G. In 2006, Xu conjectured that: for any 2-connected graph G of order n(n≥2), . In this article we show that this conjecture is not true. More precisely, we show that for any positive integer m, there exists an m-connected graph G such that . Also for every two natural numbers m and n, we determine , where K_m,n is the complete bipartite graph with part sizes m and n.