Search

An acyclic edge-coloring of a graph is a proper edge-coloring without bichromatic ( 2 -colored) cycles. The acyclic chromatic index of a graph G , denoted by a ′ ( G ) , is the least integer k such that G admits an acyclic edge-coloring using k colors. Let Δ = Δ ( G ) denote the maximum degree of a vertex in a graph G . A complete bipartite graph with n vertices on each side is denoted by K n , n . Basavaraju, Chandran and Kummini proved that a ′ ( K n , n ) ≥ n + 2 = Δ + 2 when n is odd. Basavaraju and Chandran provided an acyclic edge-coloring of K p , p using p + 2 colors and thus establishing a ′ ( K p , p ) = p + 2 = Δ + 2 when p is an odd prime. The main tool in their approach is perfect 1 -factorization of K p , p . Recently, following their approach, Venkateswarlu and Sarkar have shown that K 2 p − 1 , 2 p − 1 admits an acyclic edge-coloring using 2 p + 1 colors which implies that a ′ ( K 2 p − 1 , 2 p − 1 ) = 2 p + 1 = Δ + 2 , where p is an odd prime. In this paper, we generalize this approach and present a general framework to possibly get an acyclic edge-coloring of K n , n which possesses a perfect 1 -factorization using n + 2 = Δ + 2 colors. In this general framework, using number theoretic techniques, we show that K p 2 , p 2 admits an acyclic edge-coloring with p 2 + 2 colors and thus establishing a ′ ( K p 2 , p 2 ) = p 2 + 2 = Δ + 2 when p is an odd prime. [ABSTRACT FROM AUTHOR]

Let Γ be an abelian group and g ≥ h ≥ 2 be integers. A set A ⊂ Γ is a C h [ g ] -set if given any set X ⊂ Γ with | X | = h , and any set { k 1 , … , k g } ⊂ Γ , at least one of the translates X + k i is not contained in A . For any g ≥ h ≥ 2 , we prove that if A ⊂ { 1 , 2 , … , n } is a C h [ g ] -set in Z , then | A | ≤ ( g − 1 ) 1 / h n 1 − 1 / h + O ( n 1 / 2 − 1 / 2 h ) . We show that for any integer n ≥ 1 , there is a C 3 [ 3 ] -set A ⊂ { 1 , 2 , … , n } with | A | ≥ ( 4 − 2 / 3 + o ( 1 ) ) n 2 / 3 . We also show that for any odd prime p , there is a C 3 [ 3 ] -set A ⊂ F p 3 with | A | ≥ p 2 − p , which is asymptotically best possible. Using the projective norm graphs from extremal graph theory, we show that for each integer h ≥ 3 , there is a C h [ h ! + 1 ] -set A ⊂ { 1 , 2 , … , n } with | A | ≥ ( c h + o ( 1 ) ) n 1 − 1 / h . A set A is a weak C h [ g ] -set if we add the condition that the translates X + k 1 , … , X + k g are all pairwise disjoint. We use the probabilistic method to construct weak C h [ g ] -sets in { 1 , 2 , … , n } for any g ≥ h ≥ 2 . Lastly we obtain upper bounds on infinite C h [ g ] -sequences. We prove that for any infinite C h [ g ] -sequence A ⊂ N , we have A ( n ) = O ( n 1 − 1 / h ( log n ) − 1 / h ) for infinitely many n , where A ( n ) = | A ∩ { 1 , 2 , … , n } | . [ABSTRACT FROM AUTHOR]

Abstract: In a graph , a module is a vertex subset such that every vertex outside is adjacent to all or none of . A graph is prime if , the single-vertex sets, and are the only modules in . A prime graph is -minimal if there is some -set of vertices such that no proper induced subgraph of containing is prime. Cournier and Ille in 1998 characterized the -minimal and -minimal graphs. We characterize -minimal triangle-free graphs. As a corollary, we show that there are exactly nonisomorphic -minimal triangle-free -vertex graphs when , where denotes the nearest integer to . [Copyright &y& Elsevier]

Abstract: A graph is called -arc-regular with if acts regularly on its arc set, while is called arc-regular if . J.X. Zhou and Y.Q. Feng [Cubic one-regular graphs of order twice a square-free integer, Sci. China Ser. A 51 (2008) 1093–1100] proved that there is no cubic arc-regular graph of order four times an odd square-free integer. In this paper, we shall generalize this result by showing that there is no arc-regular -valent graph of order four times an odd square-free integer for each odd prime . Moreover, we prove that there are exactly two specific infinite families of -arc-regular graphs with a proper subgroup of . [Copyright &y& Elsevier]

Abstract: Two sets and of non-negative integers are called additive complements, if their sum contains all sufficiently large integers. Let and be the counting functions of and . Up to now, all researches on additive complements are under the assumption that and are infinite sets. In this paper, we consider the case that is a finite set. This is very different from the infinite case. [Copyright &y& Elsevier]

Abstract: Let be the th coefficient of the th cyclotomic polynomial. In part I it was proved that , in the case when is a prime power. In this paper we show that the result also holds true in the case when is an arbitrary positive integer. [Copyright &y& Elsevier]

For any prime number p , positive integers m , k , n , where n satisfies gcd (p , n) = 1 , and for any non-zero element λ 0 of the finite field F p m of cardinality p m , we prove that any λ 0 p k -constacyclic code of length p k n over the finite field F p m is monomially equivalent to a matrix-product code of a nested sequence of p k λ 0 -constacyclic codes with length n over F p m . As an application, we completely determine the Hamming distances of all negacyclic codes of length 7 ⋅ 2 l over F 7 for any integer l ≥ 3. [ABSTRACT FROM AUTHOR]