Path coverings with paths

In this paper, we give two new proofs of a result of Heinrich, Langdeau and Verrall that provide necessary and sufficient conditions for the existence of a set S of 3‐paths in K_n having the property that each 2‐path in K_n lies in exactly one path in S. These are then used to consider the case n ≡ 3 (mod 4) when no such exact covering is possible, and to solve the problem of covering (k−1)‐paths with k‐paths for all k ≥ 3. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 156–167, 2001     

Partial Degree Conditions and Cycle Coverings

Let G be a graph of order n. Let W be a subset of with , where k is a positive integer. We show that if for each , then G contains k vertex‐disjoint cycles covering W such that each of the k cycles contains at least three vertices of W.     

The chromatic numbers of double coverings of a graph

If we fix a spanning subgraph H of a graph G, we can define a chromatic number of H with respect to G and we show that it coincides with the chromatic number of a double covering of G with co-support H. We also find a few estimations for the chromatic numbers of H with respect to G.     

New lower bounds for multiple coverings

A code , where Z ₂ = {0,1}, is said to be a binary μ-fold R-covering code, if for any word there are at least μ distinct codewords which differ from v in at most R coordinates. The size of the smallest binary μ-fold R-covering code of length n is denoted by K(n, R, μ). In this paper we use integer programming and exhaustive search to improve 57 lower bounds on K(n, R, μ) for 6 ≤ n ≤ 16, 1 ≤ R ≤ 4 and 2 ≤ μ ≤ 4.      

-algebras associated with branched coverings

In this note we analyze the -algebra associated with a branched covering both as a groupoid -algebra and as a Cuntz-Pimsner algebra. We determine conditions when the algebra is simple and purely infinite. We indicate how to compute the K-theory of several examples, including one related to rational maps on the Riemann sphere.

     

All double coverings of cyclotomic fields

A double covering of a Galois extension K/F in the sense of [3] is an extension /K of degree ≤2 such that /F is Galois. In this paper we determine explicitly all double coverings of any cyclotomic extension over the rational number field in the complex number field. We get the results mainly by Galois theory and by using and modifying the results and the methods in [2] and [3]. Project 10571097 supported by NSFC     

Lower bounds for coverings of pairs by large blocks

Letnkt be positive integers, andX—a set ofn elements. LetC(n, k, t) be the smallest integerm such that there existm k-tuples ofX B ₁ B ₂,...,B _m with the property that everyt-tuple ofX is contained in at least oneB _i . It is shown that in many cases the standard lower bound forC(n, k, 2) can be improved (k sufficiently large,n/k being fixed). Some exact values ofC(n, k, 2) are also obtained.     

Linearized decomposition codes and finite integer set coverings

In this paper, we study parallel erasure correction (PEC) matrix codes capable of correcting multiple row erasures simultaneously. Our PEC codes are based on linearized decomposition (LD) of polynomials and we show that the LD codes are capable of row erasure correction using small locality sets, even if roughly half the rows are erased. We also study coverings of finite set of integers using predetermined neighbourhoods and use the covering estimate obtained, to bound the rate of LD codes.     

Self-similar sets with optimal coverings and packings

We prove that if a self-similar set E in Rn with Hausdorff dimension s satisfies the strong separation condition, then the maximal values of the Hs-density on the class of arbitrary subsets of Rn and on the class of Euclidean balls are attained, and the inverses of these values give the exact values of the Hausdorff and spherical Hausdorff measure of E. We also show that a ball of minimal density exists, and the inverse density of this ball gives the exact packing measure of E. Lastly, we show that these elements of optimal densities allow us to construct an optimal almost covering of E by arbitrary subsets of Rn, an optimal almost covering of E by balls and an optimal packing of E.     

Covering a graph with cycles passing through given edges

We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e₁, …, e_k of G, there exist k vertex-disjoint cycles C₁, …, C_k in G such that e_i ∈ E(C_i) for all i ∈ {1, …, k} and V(C₁ ∪ ···∪ C_k) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997     

On $ \pi $-hyperbolic knots and branched coverings

We prove that, for any given , a -hyperbolic knot is determined by its 2-fold and n-fold cyclic branched coverings. We also prove that a -hyperbolic knot which is not determined by its m-fold and n-fold cyclic branched coverings, , must have genus . Received: December 14, 1998.     

Closure, 2-factors,and cycle coverings in claw-free graphs

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217–224). For a claw-free graph G and its closure cl(G), we prove: (1) V(G) is covered by k cycles in G if and only if V(cl(G)) is covered by k cycles of cl(G); and (2) G has a 2-factor with at most k components if and only if cl(G) has a 2-factor with at most k components. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 109–117, 1999     

Lifting of homeomorphisms to 4-sheeted branched coverings of a disk

Let p:X→D be a simple, possibly not connected, 4-sheeted branched covering of a closed 2-dimensional disk D with n branch values A₁,…,An. The isotopy classes of homeomorphisms of D which are fixed on the boundary of D and permute the branch values form a braid group Bn. Some of these homeomorphisms can be lifted to homeomorphisms of X. They form a subgroup L(p) of finite index in Bn. For each equivalence class of coverings we find a set of generators for L(p) which contains between n and n+4 elements, depending on the equivalence class of the covering, and the generators are powers of half-twists.     

Pencils on double coverings of curves

Let X be a smooth curve of genus g. When and d ≥ π−2g+1 we show the existence of a double covering where C a smooth curve of genus π with a base-point-free pencil of degree d which is not the pull-back of a pencil on X. Received: 7 February 2007; Revised: 1 July 2008     

Combinatorial coverings from geometries over principal ideal rings

A t-(v, k, λ) covering is an incidence structure with v points, each block incident on exactly k points, such that every set of t distinct points is incident on at least λ blocks. By considering certain geometries over finite principal ideal rings, we construct infinite families of t-(v, k, λ) coverings having many interesting combinatorial properties. © 1999 John & Sons, Inc. J Combin Designs 7: 247–268, 1999     

Compact coverings for Baire locally convex spaces

Very recently Tkachuk has proved that for a completely regular Hausdorff space X the space Cp(X) of continuous real-valued functions on X with the pointwise topology is metrizable, complete and separable iff Cp(X) is Baire (i.e. of the second Baire category) and is covered by a family of compact sets such that Kα⊂Kβ if α?β. Our general result, which extends some results of De Wilde, Sunyach and Valdivia, states that a locally convex space E is separable metrizable and complete iff E is Baire and is covered by an ordered family of relatively countably compact sets. Consequently every Baire locally convex space which is quasi-Suslin is separable metrizable and complete.