disjoint cycles containing specified independent vertices

Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ₂(G)n+k-1. Let v₁,…,v_k be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C₁,…,C_k with v_iV(C_i) for all 1ik.Then G has k vertex-disjoint cycles such that

(i) for all 1ik.

(ii) , and

(iii) At least k-1 of the k cycles are triangles.

The condition of degree sum σ₂(G)n+k-1 is sharp.

On shredders and vertex connectivity augmentation

We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight.     

Existence of HSOLSSOMs of type

In this paper we investigate the existence of holey self-orthogonal Latin squares with a symmetric orthogonal mate of type 2ⁿu¹ (HSOLSSOM(2ⁿu¹)). For u2, necessary conditions for existence of such an HSOLSSOM are that u must be even and n3u/2+1. Xu Yunqing and Hu Yuwang have shown that these HSOLSSOMs exist whenever either (1) n9 and n3u/2+1 or (2) n263 and n2(u-2). In this paper we show that in (1) the condition n9 can be extended to n30 and that in (2), the condition n263 can be improved to n4, except possibly for 19 pairs (n,u), the largest of which is (53,28).     

Algorithms for extracting motifs from biological weighted sequences

In this paper we present three algorithms for the Motif Identification Problem in Biological Weighted Sequences. The first algorithm extracts repeated motifs from a biological weighted sequence. The motifs correspond to repetitive words which are approximately equal, under a Hamming distance, with probability of occurrence 1/k, where k is a small constant. The second algorithm extracts common motifs from a set of N2 weighted sequences. In this case, the motifs consists of words that must occur with probability 1/k, in 1qN distinct sequences of the set. The third algorithm extracts maximal pairs from a biological weighted sequence. A pair in a sequence is the occurrence of the same word twice. In addition, the algorithms presented in this paper improve previous work on these problems.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

The maximum spectral radius of -free graphs of given order and size

Suppose that G is a graph with n vertices and m edges, and let μ be the spectral radius of its adjacency matrix.Recently we showed that if G has no 4-cycle, then μ²-μn-1, with equality if and only if G is the friendship graph.Here we prove that if m9 and G has no 4-cycle, then μ²m, with equality if G is a star. For 4m8 this assertion fails.     

Uniform Kazhdan constant for some families of linear groups

Let R be a ring generated by l elements with stable range r. Assume that the group EL_d(R) has Kazhdan constant ₀>0 for some dr+1. We prove that there exist (₀,l)>0 and , s.t. for every nd, EL_n(R) has a generating set of order k and a Kazhdan constant larger than . As a consequence, we obtain for where n3, a Kazhdan constant which is independent of n w.r.t. generating set of a fixed size.     

Arithmetic progressions consisting of unlike powers

In this paper we present some new results about unlike powers in arithmetic progression. We prove among other things that for given k 4 and L 3 there are only finitely many arithmetic progressions of the form with x_i , gcd(x₀, x_l) = 1 and 2 l_i L for i = 0, 1, …, k − 1. Furthermore, we show that, for L = 3, the progression (1, 1,…, 1) is the only such progression up to sign. Our proofs involve some well-known theorems of Faltings [9], Darmon and Granville [6] as well as Chabauty's method applied to superelliptic curves.     

Continued fractions with multiple limits

For integers m2, we study divergent continued fractions whose numerators and denominators in each of the m arithmetic progressions modulo m converge. Special cases give, among other things, an infinite sequence of divergence theorems, the first of which is the classical Stern–Stolz theorem.We give a theorem on a class of Poincaré-type recurrences which shows that they tend to limits when the limits are taken in residue classes and the roots of their characteristic polynomials are distinct roots of unity.We also generalize a curious q-continued fraction of Ramanujan's with three limits to a continued fraction with k distinct limit points, k2. The k limits are evaluated in terms of ratios of certain q-series.Finally, we show how to use Daniel Bernoulli's continued fraction in an elementary way to create analytic continued fractions with m limit points, for any positive integer m2.     

Hilbert's Tenth Problem for function fields of varieties over number fields and p-adic fields

Let k be a subfield of a p-adic field of odd residue characteristic, and let be the function field of a variety of dimension n1 over k. Then Hilbert's Tenth Problem for is undecidable. In particular, Hilbert's Tenth Problem for function fields of varieties over number fields of dimension 1 is undecidable.     

On the structure of semi-invariant polynomials in Ore extensions

Let D be an X-outer S-derivation of a prime ring R, where S is an automorphism of R. The following is proved among other things: The degree of the minimal semi-invariant polynomial of the Ore extension R[X;S,D] is ν if charR=0, and is p^kν for some k0 if charR=p2, where ν is the least integer ν1 such that S^νDS^−ν−D is X-inner. A similar result holds for cv-polynomials. These are done by introducing the new notion of k-basic polynomials for each integer k0, which enable us to analyze semi-invariant polynomials inductively.     

An iterative approximation procedure for the distribution of the maximum of a random walk

Let I(F) be the distribution function (d.f.) of the maximum of a random walk whose i.i.d. increments have the common d.f. F and a negative mean. We derive a recursive sequence of embedded random walks whose underlying d.f.'s F_k converge to the d.f. of the first ladder variable and satisfy FF₁F₂ on [0,∞) and I(F)=I(F₁)=I(F₂)=. Using these random walks we obtain improved upper bounds for the difference of I(F) and the d.f. of the maximum of the random walk after finitely many steps.     

Perfect codes in direct products of cycles—a complete characterization

Let be a direct product of cycles. It is known that for any r1, and any n2, each connected component of G contains a so-called canonical r-perfect code provided that each ℓ_i is a multiple of rⁿ+(r+1)ⁿ. Here we prove that up to a reasonably defined equivalence, these are the only perfect codes that exist.     

Algorithms for graphs of bounded treewidth via orthogonal range searching

We show that, for any fixed constant k3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlog^k−1n) time.We also show that, for any fixed constant k2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlog^k+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.     

Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion

An efficient method to generate all edge sets XE of a graph G=(V,E), which are vertex-disjoint unions of cycles, is presented. It can be tweaked to generate (i) all cycles, (ii) all cycles of cardinality 5, (iii) all chordless cycles, (iv) all Hamiltonian cycles.     

The perfect matching polytope and solid bricks

The perfect matching polytope of a graph G is the convex hull of the set of incidence vectors of perfect matchings of G. Edmonds (J. Res. Nat. Bur. Standards Sect. B 69B 1965 125) showed that a vector x in Q^E belongs to the perfect matching polytope of G if and only if it satisfies the inequalities: (i) x0 (non-negativity), (ii) x(∂(v))=1, for all vV (degree constraints) and (iii) x(∂(S))1, for all odd subsets S of V (odd set constraints). In this paper, we characterize graphs whose perfect matching polytopes are determined by non-negativity and the degree constraints. We also present a proof of a recent theorem of Reed and Wakabayashi.     

On the code generated by the incidence matrix of points and k-spaces in and its dual

In this paper, we study the p-ary linear code C_k(n,q), q=p^h, p prime, h1, generated by the incidence matrix of points and k-dimensional spaces in PG(n,q). For kn/2, we link codewords of C_k(n,q)C_k(n,q) of weight smaller than 2q^k to k-blocking sets. We first prove that such a k-blocking set is uniquely reducible to a minimal k-blocking set, and exclude all codewords arising from small linear k-blocking sets. For k<n/2, we present counterexamples to lemmas valid for kn/2. Next, we study the dual code of C_k(n,q) and present a lower bound on the weight of the codewords, hence extending the results of Sachar [H. Sachar, The F_p span of the incidence matrix of a finite projective plane, Geom. Dedicata 8 (1979) 407–415] to general dimension.     

Hamiltonicity and restricted block-intersection graphs of -designs

Given a combinatorial design with block set , its traditional block-intersection graph is the graph having vertex set such that two vertices b₁ and b₂ are adjacent if and only if b₁ and b₂ have non-empty intersection. In this paper, we consider the S-block-intersection graph, in which two vertices b₁ and b₂ are adjacent if and only if |b₁∩b₂|S. As our main result, we prove that {1,2,…,t−1}-block-intersection graphs of t-designs with parameters (v,t+1,λ) are Hamiltonian whenever t3 and vt+3, except possibly when (v,t){(8,5),(7,4),(7,3),(6,3)}.     

A new kind of graph coloring

A proper k-coloring C¹,C²,…,C^k of a graph G is called strong if, for every vertex uV(G), there exists an index i{1,2,…,k} such that u is adjacent to every vertex of Cⁱ. We consider classes of strongly k-colorable graphs and show that the recognition problem of is NP-complete for every k4, but it is polynomial-time solvable for k=3. We give a characterization of in terms of forbidden induced subgraphs. Finally, we solve the problem of uniqueness of a strong 3-coloring.