A note on the automorphism groups of cubic Cayley graphs of finite simple groups

For a finite group G, a Cayley graph on G is said to be normal if . In this note, we prove that connected cubic non-symmetric Cayley graphs of the ten finite non-abelian simple groups G in the list of non-normal candidates given in [X.G. Fang, C.H. Li, J. Wang, M.Y. Xu, On cubic Cayley graphs of finite simple groups, Discrete Math. 244 (2002) 67-75] are normal.     

Linear choosability of sparse graphs

A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , of sparse graphs. The maximum average degree of a graph G, denoted mad(G), is the maximum of the average degrees of all subgraphs of G. It is clear that any graph G with maximum degree Δ(G) satisfies . In this paper, we prove the following results: (1) if and Δ(G)≥3, then , and we give an infinite family of examples to show that this result is best possible; (2) if and Δ(G)≥9, then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if G is planar and has girth at least 5, then .     

Game colouring of the square of graphs

This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if G is a forest of maximum degree Δ≥9, then , and there are forests G with . It is also proved that for an outerplanar graph G of maximum degree Δ, , and for a planar graph G of maximum degree Δ, .     

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 .     

Quasi-convex density and determining subgroups of compact abelian groups

For an abelian topological group G, let denote the dual group of all continuous characters endowed with the compact open topology. Given a closed subset X of an infinite compact abelian group G such that w(X)<w(G), and an open neighborhood U of 0 in T, we show that . (Here, w(G) denotes the weight of G.) A subgroup D of G determines G if the map defined by r(χ)=χ?D for , is an isomorphism between and . We prove that

     

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.     

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.     

Remarks on a generalization of the Davenport constant

A generalization of the Davenport constant is investigated. For a finite abelian group G and a positive integer k, let denote the smallest ? such that each sequence over G of length at least ? has k disjoint non-empty zero-sum subsequences. For general G, expanding on known results, upper and lower bounds on these invariants are investigated and it is proved that the sequence is eventually an arithmetic progression with difference exp(G), and several questions arising from this fact are investigated. For elementary 2-groups, is investigated in detail; in particular, the exact values are determined for groups of rank four and five (for rank at most three they were already known).     

Directed cyclic Hamiltonian cycle systems of the complete symmetric digraph

In this paper, we prove that directed cyclic Hamiltonian cycle systems of the complete symmetric digraph, , exist if and only if n is odd with n≠15 and n≠p^α for p an odd prime and α≥2 or with n≠2p^α for p an odd prime and α≥1. We also show that directed cyclic Hamiltonian cycle systems of the complete symmetric digraph minus a set of n/2 vertex-independent digons, (K_n−I)^∗, exist if and only if .     

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.     

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

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.     

Upper bounds on the linear chromatic number of a graph

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Δ(G). In this paper we prove the following results: (1) ; (2) if Δ(G)≤4; (3) if Δ(G)≤5; (4) if G is planar and Δ(G)≥52.     

On the circumference of a graph and its complement

Let G be a graph of order n and circumference c(G). Let be the complement of G. We prove that and show sharpness of this bound.     

Ore-type conditions implying 2-factors consisting of short cycles

For every graph G, let . The main result of the paper says that every n-vertex graph G with contains each spanning subgraph H all whose components are isomorphic to graphs in . This generalizes the earlier results of Justesen, Enomoto, and Wang, and is a step towards an Ore-type analogue of the Bollobás-Eldridge-Catlin Conjecture.     

Congruences involving Bernoulli polynomials

Let {B_n(x)} be the Bernoulli polynomials. In the paper we establish some congruences for , where p is an odd prime and x is a rational p-integer. Such congruences are concerned with the properties of p-regular functions, the congruences for and the sum , where h(d) is the class number of the quadratic field of discriminant d and p-regular functions are those functions f such that are rational p-integers and for n=1,2,3,… . We also establish many congruences for Euler numbers.     

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.     

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

Remarks on Hardy spaces defined by non-smooth approximate identity

We study in this paper some relations between Hardy spaces which are defined by non-smooth approximate identity ?(x), and the end-point Triebel-Lizorkin spaces (1?q?∞). First, we prove that for compact ? which satisfies a slightly weaker condition than Fefferman and Stein's condition. Then we prove that non-trivial Hardy space defined by approximate identity ? must contain Besov space . Thirdly, we construct certain functions and a function such that Daubechies wavelet function but .