On the chromatic number of circulant graphs

Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(Z_N,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on Z_N with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs.     

Nonsingularity of least common multiple matrices on gcd-closed sets

Let n be a positive integer. Let S={x₁,…,x_n} be a set of n distinct positive integers. The least common multiple (LCM) matrix on S, denoted by [S], is defined to be the n×n matrix whose (i,j)-entry is the least common multiple [x_i,x_j] of x_i and x_j. The set S is said to be gcd-closed if for any x_i,x_j∈S,(x_i,x_j)∈S. For an integer m>1, let ω(m) denote the number of distinct prime factors of m. Define ω(1)=0. In 1997, Qi Sun conjectured that if S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. In this paper, we settle completely Sun's conjecture. We show the following result: (i). If S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. Namely, Sun's conjecture is true; (ii). For each integer r?3, there exists a gcd-closed set S satisfying max_x∈S{ω(x)}=r, such that the LCM matrix [S] is singular.     

Divisibility properties of power GCD matrices and power LCM matrices

Let a,b and n be positive integers and the set S={x₁,…,x_n} of n distinct positive integers be a divisor chain (i.e. there exists a permutation σ on {1,…,n} such that x_σ(1)|…|x_σ(n)). In this paper, we show that if a|b, then the ath power GCD matrix (S^a) having the ath power (x_i,x_j)^a of the greatest common divisor of x_i and x_j as its i,j-entry divides the bth power GCD matrix (S^b) in the ring M_n(Z) of n×n matrices over integers. We show also that if a?b and n?2, then the ath power GCD matrix (S^a) does not divide the bth power GCD matrix (S^b) in the ring M_n(Z). Similar results are also established for the power LCM matrices.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

Isomorphism of circulant graphs and digraphs

Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v₀, v₁,…, v_n?1} and edge set E satisfies v_iv_j?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that $\text{G(n, S) ? G(n, S′)}$ if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p², and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p² where p is an odd prime, or n is divisible by 2⁴.     

Nonsingularity of matrices associated with classes of arithmetical functions on lcm-closed sets

Let S = {x₁, … , x_n} be a set of n distinct positive integers and f be an arithmetical function. Let [f(x_i, x_j)] denote the n × n matrix having f evaluated at the greatest common divisor (x_i, x_j) of x_i and x_j as its i, j-entry and (f[x_i, x_j]) denote the n × n matrix having f evaluated at the least common multiple [x_i, x_j] of x_i and x_j as its i, j-entry. The set S is said to be lcm-closed if [x_i, x_j] ∈ S for all 1 ? i, j ? n. For an integer x > 1, let ω(x) denote the number of distinct prime factors of x. Define ω(1) = 0. In this paper, we show that if S = {x₁, … , x_n} is an lcm-closed set satisfying , and if f is a strictly increasing (resp. decreasing) completely multiplicative function, or if f is a strictly decreasing (resp. increasing) completely multiplicative function satisfying (resp. f(p) ? p) for any prime p, then the matrix [f(x_i, x_j)] (resp. (f[x_i, x_j])) defined on S is nonsingular. By using the concept of least-type multiple introduced in [S. Hong, J. Algebra 281 (2004) 1-14], we also obtain reduced formulas for det(f(x_i, x_j)) and det(f[x_i, x_j]) when f is completely multiplicative and S is lcm-closed. We also establish several results about the nonsingularity of LCM matrices and reciprocal GCD matrices.     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

On monotone functions of tree structures

Let T be a rooted tree structure with n nodes a₁,…,a_n. A function f: {a₁,…,a_n} into {1 < ? < k} is called monotone if whenever a_i is a son of a_j, then f(a_i) ≥ f(a_j). The average number of monotone bijections is determined for several classes of tree structures. If k is fixed, for the average number of monotone functions asymptotic equivalents of the form c · ?^?nn^{?$\text{3}\text{2}$} (n → ∞) are obtained for several classes of tree structures.     

Divisibility of determinants of power GCD matrices and power LCM matrices on finitely many quasi-coprime divisor chains

Let a, n ? 1 be integers and S = {x₁, … , x_n} be a set of n distinct positive integers. The matrix having the ath power (x_i, x_j)^a of the greatest common divisor of x_i and x_j as its i, j-entry is called ath power greatest common divisor (GCD) matrix defined on S, denoted by (S^a). Similarly we can define the ath power LCM matrix [S^a]. We say that the set S consists of finitely many quasi-coprime divisor chains if we can partition S as S = S₁ ∪ ? ∪ S_k, where k ? 1 is an integer and all S_i (1 ? i ? k) are divisor chains such that (max(S_i), max(S_j)) = gcd(S) for 1 ? i ≠ j ? k. In this paper, we first obtain formulae of determinants of power GCD matrices (S^a) and power LCM matrices [S^a] on the set S consisting of finitely many quasi-coprime divisor chains with gcd(S) ∈ S. Using these results, we then show that det(S^a)∣det(S^b), det[S^a]∣det[S^b] and det(S^a)∣det[S^b] if a∣b and S consists of finitely many quasi-coprime divisor chains with gcd(S) ∈ S. But such factorizations fail to be true if such divisor chains are not quasi-coprime.     

The convexity spectra of graphs

Let D be a connected oriented graph. A set S⊆V(D) is convex in D if, for every pair of vertices x,y∈S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity numbercon(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that S_C(G)={con(D):D is an orientation of G} and S_SC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n?4, 1?a?n-2, and a≠2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_SC(G)={a,n-1} and there is no connected graph G of order n?3 with S_SC(G)={n-1}. Then, we determine that S_C(K₃)={1,2}, S_C(K₄)={1,3}, S_SC(K₃)=S_SC(K₄)={1}, S_C(K₅)={1,3,4}, S_C(K₆)={1,3,4,5}, S_SC(K₅)=S_SC(K₆)={1,3}, S_C(K_n)={1,3,5,6,…,n-1}, S_SC(K_n)={1,3,5,6,…,n-2} for n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.     

On some invariants in numerical semigroups and estimations of the order bound

Let S={s _i } _i∈??? be a numerical semigroup. For s _i ∈S, let ν(s _i ) denote the number of pairs (s _i ?s _j ,s _j )∈S ². When S is the Weierstrass semigroup of a family $\{\mathcal{C}_{i}\}_{i\in\mathbb{N}}Let S={s _i } _i∈ℕ⊆ℕ be a numerical semigroup. For s _i ∈S, let ν(s _i ) denote the number of pairs (s _i −s _j ,s _j )∈S ². When S is the Weierstrass semigroup of a family {C_i}_{i ? \mathbbN}\{\mathcal{C}_{i}\}_{i\in\mathbb{N}} of one-point algebraic-geometric codes, a good bound for the minimum distance of the code C_i\mathcal{C}_{i} is the Feng and Rao order bound d _ORD (C _i ). It is well-known that there exists an integer m such that d _ORD (C _i )=ν(s _i+1) for each i≥m. By way of some suitable parameters related to the semigroup S, we find upper bounds for m and we evaluate m exactly in many cases. Further we conjecture a lower bound for m and we prove it in several classes of semigroups.     

THE EDGE-CHROHATIC NUMBER OF A CIRCULANT

ABSTRACT

The circulant graph C_p > a₁,…, a_k < with 0 > a₁ >…> a_k >(pt1)/2 has p vertices labeled 0,1,…,p-1 and x and y are adjacent if and only if x—y = ± a_i (mod p) for some i. We prove the following regarding the chromatic index of a circulant: if d = gcd (a₁,…, a_k, p), then x' (C_p > a_l,…,a_k) = Δ(C p > a₁,…,a_k) if and only if p/d is even.     

On constant discrete programming problems

Let H be a subset of the set S_n of all permutations

$\text{1}\text{2}\text{???}\text{n}\text{s(1)}\text{s(2)}\text{???}\text{s(n)}$

C=6c_ij6 a real n?n matrix L_c(s)=c_1s(1)+c_2s(2)+???+c_ns(n) for s ? H. A pair (H, C) is the existencee of reals a₁,b₁,a₂,b₂,…a_n,b_n, for which c_ij=a₁+b_j if (i,j)?D(H), where D(H)={(i,j):(?h?H)(j=h(i))}.For a pair (H,C) the specifity of it is proved in the case, when H is either a special cyclic class of permutations or a special union of cyclic classes. Specific pairs with minimal sets H are in some sense described.     

A random intersection digraph: Indegree and outdegree distributions

Let S(1),…,S(n),T(1),…,T(n) be random subsets of the set [m]={1,…,m}. We consider the random digraph D on the vertex set [n] defined as follows: the arc i→j is present in D whenever S(i)∩T(j)≠0?. Assuming that the pairs of sets (S(i),T(i)), 1≤i≤n, are independent and identically distributed, we study the in- and outdegree distributions of a typical vertex of D as n,m→∞.     

Selection principle for pointwise bounded sequences of functions

For a number ? > 0 and a real function f on an interval [a, b], denote by N(?, f, [a, b]) the least upper bound of the set of indices n for which there is a family of disjoint intervals [a _i , b _i ], i = 1, …, n, on [a, b] such that |f(a _i ) ? f(b _i )| > ? for any i = 1, …, n (sup Ø = 0). The following theorem is proved: if {f _j } is a pointwise bounded sequence of real functions on the interval [a, b] such that n(?) ≡ lim sup _j→∞ N(?, f _j , [a, b]) < ∞ for any ? > 0, then the sequence {f _j } contains a subsequence which converges, everywhere on [a, b], to some function f such that N(?, f, [a, b]) ≤ n(?) for any ? > 0. It is proved that the main condition in this theorem related to the upper limit is necessary for any uniformly convergent sequence {f _j } and is “almost” necessary for any everywhere convergent sequence of measurable functions, and many pointwise selection principles generalizing Helly’s classical theorem are consequences of our theorem. Examples are presented which illustrate the sharpness of the theorem.     

A generalization of Sperner’s theorem and an application to graph orientations

A generalization of Sperner’s theorem is established: For a multifamily M={Y₁,…,Y_p} of subsets of {1,…,n} in which the repetition of subsets is allowed, a sharp lower bound for the number φ(M) of ordered pairs (i,j) satisfying i≠j and Y_i⊆Y_j is determined. As an application, the minimum average distance of orientations of complete bipartite graphs is determined.     

Rose window graphs underlying rotary maps

Given natural numbers n≥3 and 1≤a,r≤n−1, the rose window graph R_n(a,r) is a quartic graph with vertex set {x_i∣i∈Z_n}∪{y_i∣i∈Z_n} and edge set {{x_i,x_i+1}∣i∈Z_n}∪{{y_i,y_i+r}∣i∈Z_n}∪{{x_i,y_i}∣i∈Z_n}∪{{x_i+a,y_i}∣i∈Z_n}. In this paper rotary maps on rose window graphs are considered. In particular, we answer the question posed in [S. Wilson, Rose window graphs, Ars Math. Contemp. 1 (2008), 7-19. http://amc.imfm.si/index.php/amc/issue/view/5] concerning which of these graphs underlie a rotary map.     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].