Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

Steiner centers in graphs

The Steiner distance of a set S of vertices in a connected graph G is the minimum size among all connected subgraphs of G containing S. For n ≥ 2, the n-eccentricity e_n(ν) of a vertex ν of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contains ν. The n-diameter of G is the maximum n-eccentricity among the vertices of G while the n-radius of G is the minimum n-eccentricity. The n-center of G is the subgraph induced by those vertices of G having minimum n-eccentricity. It is shown that every graph is the n-center of some graph. Several results on the n-center of a tree are established. In particular, it is shown that the n-center of a tree is a tree and those trees that are n-centers of trees are characterized.     

Small quasimultiple affine and projective planes: Some improved bounds

We improve the known bounds on r(n): = min {λ| an (n², n, λ)-RBIBD exists} in the case where n + 1 is a prime power. In such a case r(n) is proved to be at most n + 1. If, in addition, n − 1 is the product of twin prime powers, then r(n) ${\ \le \ }{n \over 2}$. We also improve the known bounds on p(n): = min{λ| an (n² + n + 1, n + 1, λ)-BIBD exists} in the case where n² + n + 1 is a prime power. In such a case p(n) is bounded at worst by but better bounds could be obtained exploiting the multiplicative structure of GF(n² + n + 1). Finally, we present an unpublished construction by M. Greig giving a quasidouble affine plane of order n for every positive integer n such that n − 1 and n + 1 are prime powers. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 337–345, 1998     

Fixed Points of Automorphisms of Graphs with 1 – Factorizations

We consider sets of fixed points of finite simple undirected connected graphs with 1 – factorizations. The maximum number of fixed points of complete graphs K_2n (n > 2) is n if n ≡ 0 mod 4, n — 1 if n ≡ 3 mod 4 or n ≡ 5 mod 12, n — 2 if n ≡ 2 mod 4, n — 3 if n ≡ 1 mod 4 and n ≢ 5 (mod 12). The maximum number of fixed points of 1 – factorizations of (non – complete) graphs with 2n vertices is less than or equal to n. If n is a prime number, then there are graphs with 2n vertices whose 1 – factorizations have automorphisms with n fixed points. Moreover, a result on the structure of a group of fixed – point – free automorphisms is presented.     

Fully invariant transformations and associated groups

It is well known that the symmetric group S _ntogether with one idempotent of rank n- 1 on a finite n-element set Nserves as a set of generators for the semigroup T _nof all the total transformations on N. It is also well known that the singular part Sing _n of T _n can be generated by a set of idempotents of rank n- 1. The purpose of this paper is to begin an investigation of the way in which Sing_nand its subsemigroups can be generated by the conjugates of a subset of elements of T _n by a subgroup of S _n . We look for the smallest subset of elements of T _n that will serve and, correspondingly, for a characterization of those subgroups of S _n that will serve. Using some techniques from graph theory we prove our main result:the conjugates of a single transformation of rank n- 1 under Gsuffice to generate Sing_nif and only if Gis what we define to be a 2-block transitive subgroup of S _n .     

On Generalizations of Prime Ideals (II)

Let R be a commutative ring with identity. We say that a proper ideal P of R is (n ? 1, n)-weakly prime (n ≥ 2) if 0 ≠ a ₁…a _n  ∈ P implies a ₁…a _i?1 a _i+1…a _n  ∈ P for some i ∈ {1,…, n}, where a ₁,…, a _n  ∈ R. In this article, we study (n ? 1, n)-weakly prime ideals. A number of results concerning (n ? 1, n)-weakly prime ideals and examples of (n ? 1, n)-weakly prime ideals are given. Rings with the property that for a positive integer n such that 2 ≤ n ≤ 5, every proper ideal is (n ? 1, n)-weakly prime are characterized. Moreover, it is shown that in some rings, nonzero (n ? 1, n)-weakly prime ideals and (n ? 1, n)-prime ideals coincide.     

On the construction of odd cycle systems

Three obvious necessary conditions for the existence of a k-cycle system of order n are that if n > 1 then n ? k, n is odd, and 2k divides n(n ? 1). We show that if these necessary conditions are sufficient for all n satisfying k ? n < 3k then they are sufficient for all n. In particular, there exists a 15-cycle system of order n if and only if n ≡ 1, 15, 21, or 25 (mod 30), and there exists a 21-cycle system of order n if and only if n ≡ 1, 7, 15, or 21 (mod 42), n ≠ 7. 15.     

Resolvable Coverings of 2-Paths by Cycles

 Let K _n be the complete graph on n vertices. A C(n,k,λ) design is a multiset of k-cycles in K _n in which each 2-path (path of length 2) of K _n occurs exactly λ times. A C(lk,k,1) design is resolvable if its k-cycles can be partitioned into classes so that every vertex appears exactly once in each class. A C(n,n,1) design gives a solution of Dudeney's round table problem. It is known that there exists a C(n,n,1) design when n is even and there exists a C(n,n,2) design when n is odd. In general the problem of constructing a C(n,n,1) design is still open when n is odd. Necessary and sufficient conditions for the existence of C(n,k,λ) designs and resolvable C(lk,k,1) designs are known when k=3,4. In this paper, we construct a resolvable C(n,k,1) design when n=p ^e +1 ( p is a prime number and e≥1) and k is any divisor of n with k≠1,2. Received: October, 2001 Final version received: September 4, 2002 RID="*" ID="*" This research was supported in part by Grant-in-Aid for Scientific Research (C) Japan     

On n-Absorbing Ideals of Commutative Rings

Let R be a commutative ring with 1 ≠ 0 and n a positive integer. In this article, we study two generalizations of a prime ideal. A proper ideal I of R is called an n-absorbing (resp., strongly n-absorbing) ideal if whenever x ₁…x _n+1 ∈ I for x ₁,…, x _n+1 ∈ R (resp., I ₁…I _n+1 ? I for ideals I ₁,…, I _n+1 of R), then there are n of the x _i 's (resp., n of the I _i 's) whose product is in I. We investigate n-absorbing and strongly n-absorbing ideals, and we conjecture that these two concepts are equivalent. In particular, we study the stability of n-absorbing ideals with respect to various ring-theoretic constructions and study n-absorbing ideals in several classes of commutative rings. For example, in a Noetherian ring every proper ideal is an n-absorbing ideal for some positive integer n, and in a Prüfer domain, an ideal is an n-absorbing ideal for some positive integer n if and only if it is a product of prime ideals.     

Path numbers of tournaments

A family of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of | | over all path decompositions of T. In this paper it is shown that if n is even, then there is a tournament on n vertices with path number k if and only if n/2 k n²/4, k an integer. It is also shown that if n is odd and T is a tournament on n vertices, then (n + 1)/2 pn(T) (n² − 1)/4. Moreover, if k is an integer satisfying (i) (n + 1)/2 k n − 1 or (ii) n < k (n² − 1)/4 and k is even, then a tournament on n vertices having path number k is constructed. It is conjectured that there are no tournaments of odd order n with odd path number k for n k < (n² − 1)/4.     

Cluster tilting for higher Auslander algebras

The concept of cluster tilting gives a higher analogue of classical Auslander correspondence between representation-finite algebras and Auslander algebras. The n-Auslander–Reiten translation functor τn plays an important role in the study of n-cluster tilting subcategories. We study the category Mn of preinjective-like modules obtained by applying τn to injective modules repeatedly. We call a finite-dimensional algebra Λ n-complete if for an n-cluster tilting object M. Our main result asserts that the endomorphism algebra EndΛ(M) is (n+1)-complete. This gives an inductive construction of n-complete algebras. For example, any representation-finite hereditary algebra Λ(1) is 1-complete. Hence the Auslander algebra Λ(2) of Λ(1) is 2-complete. Moreover, for any n?1, we have an n-complete algebra Λ(n) which has an n-cluster tilting object M(n) such that Λ(n+1)=EndΛ(n)(M(n)). We give the presentation of Λ(n) by a quiver with relations. We apply our results to construct n-cluster tilting subcategories of derived categories of n-complete algebras.     

Average-case results on heapsort

A new algorithm for rearranging a heap is presented and analysed in the average case. The average case upper bound for deleting the maximum element of a random heap is improved, and is shown to be less than [logn]+0.299+M(n) comparisons, *) whereM(n) is between 0 and 1. It is also shown that a heap can be constructed using 1.650n+O(logn) comparisons with this algorithm, the best result for any algorithm which does not use any extra space. The expected time to sortn elements is argued to be less thann logn+0.670n+O(logn), while simulation result points at an average case ofn log n+0.4n which will make it the fastest in-place sorting algorithm. The same technique is used to show that the average number of comparisons when deleting the maximum element of a heap using Williams' algorithm for rearrangement is 2([logn]–1.299+L(n)) whereL(n) also is between 0 and 1, and the average cost for Floyd-Williams Heapsort is at least 2nlogn–3.27n, counting only comparisons. An analysis of the number of interchanges when deleting the maximum element of a random heap, which is the same for both algorithms, is also presented.     

A-identities for upper triangular matrices: A question of Henke and Regev

Let K be a field of characteristic 0, and let UT _n (K) be the algebra of n × n upper triangular matrices over K. We denote by P _n the vector space of all multilinear polynomials of degree n in x ₁, …, x _n in the free associative algebra K(X). Then P _n is a left S _n -module where the symmetric group S _n acts on P _n by permuting the variables. The S _n -modules P _n and KS _n are canonically isomorphic, a fact that lets us employ the representation theory in the study of algebras with polynomial identities. Denote by A _n the alternative subgroup of S _n . One may study KA _n and its isomorphic copy in P _n with the corresponding action of A _n . Henke and Regev studied A-identities. They described the A-codimensions of the Grassmann algebra and conjectured a finite generating set of the A-identities for E. In an earlier paper we answered in the affirmative their conjecture. Another problem posed by Henke and Regev concerned the minimal degree of an A-identity satisfied by the full matrix algebra M _n (K). They asked whether this minimal degree equals 2n+2. In this paper we show that this is not the case as long as n ≥ 6. Our main result consists in computing a lower bound for the minimal degree d(n) of an A-identity satisfied by the algebra UT _n (K). It turns out that, given any positive integer k, there exists n ₀ such that d(n) > 2n + k for all n > n ₀. Moreover, we compute d(n) for n ≤ 4 and for n = 6. It turns out that d(6) = 15 > 2 × 6 + 2. We have reasons to believe that for every n, d(n) = [(5n + 1)/2] holds, where as usual [x] stands for the integer part of the real number x, that is the largest integer ≤ x.     

On digraphs without antidirected cycles

Let t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n ? 1)] ≤ t(n) ≤ 1/2 (n ? 1) for n ≥ 5. Let t_r (n) denote the corresponding quantity for r-colorable digraphs. We show that [16/5(n ? 1)] ≤ t₅(n) ≤ t₆(n) ≤ 10/3(n ? 1) for n ≥ 5 and that t₄(n) = 3(n ? 1) for n ≥ 3.     

The Arcsine Law

Let N _n denote the number of positive sums in the first n trials in a random walk (S _i) and let L _n denote the first time we obtain the maximum in S ₀,..., S _n. Then the classical equivalence principle states that N _n and L _n have the same distribution and the classical arcsine law gives necessary and sufficient condition for (1/n) L _n or (1/n) N _n to converge in law to the arcsine distribution. The objective of this note is to provide a simple and elementary proof of the arcsine law for a general class of integer valued random variables (T _n) and to provide a simple an elementary proof of the equivalence principle for a general class of integer valued random vectors (N _n, L _n).     

Tripartite Ramsey numbers for paths

In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P_2n+1,P_2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K_3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007     

Latin Squares without Orthogonal Mates

In 1779 Euler proved that for every even n there exists a latin square of order n that has no orthogonal mate, and in 1944 Mann proved that for every n of the form 4k + 1, k ≥ 1, there exists a latin square of order n that has no orthogonal mate. Except for the two smallest cases, n = 3 and n = 7, it is not known whether a latin square of order n = 4k + 3 with no orthogonal mate exists or not. We complete the determination of all n for which there exists a mate-less latin square of order n by proving that, with the exception of n = 3, for all n = 4k + 3 there exists a latin square of order n with no orthogonal mate. We will also show how the methods used in this paper can be applied more generally by deriving several earlier non-orthogonality results.     

An intermediate value theorem for graphs with given automorphism group

For a positive integer n and a finite group G, let the symbols e(G, n) and E(G, n) denote, respectively, the smallest and the greatest number of lines among all n-point graphs with automorphism group G. We say that the Intermediate Value Theorem (IVT) holds for G and n, if for each e satisfying e(G, n)≤e≤E(G, n), there exists an n-point graph with group G and e lines. The main result of this paper states that for every group G the IVT holds for all sufficiently large n. We also prove that the IVT holds for the identity group and all n, and exhibit examples of groups for which the IVT fails to hold for small values of n.     

Finiteness of integral values for the ratio of two linear recurrences

Let {F(n)} _{n ∈ N} ,{G(n)} _{n ∈ N} , be linear recurrent sequences. In this paper we are concerned with the well-known diophantine problem of the finiteness of the set ? of natural numbers n such that F(n)/G(n) is an integer. In this direction we have for instance a deep theorem of van der Poorten; solving a conjecture of Pisot, he established that if ? coincides with N, then {F(n)/G(n)} _{n ∈ N} is itself a linear recurrence sequence. Here we shall prove that if ? is an infinite set, then there exists a nonzero polynomial P such that P(n)F(n)/G(n) coincides with a linear recurrence for all n in a suitable arithmetic progression. Examples like F(n)=2 ⁿ -2, G(n)=n+2 ⁿ +(-2) ⁿ , show that our conclusion is in a sense best-possible. In the proofs we introduce a new method to cope with a notorious crucial difficulty related to the existence of a so-called dominant root. In an appendix we shall also prove a zero-density result for ? in the cases when the polynomial P cannot be taken a constant. Oblatum 12-XI-2001 & 31-I-2002?Published online: 29 April 2002