Circle Covering With a Margin

The problem of the thinnest (i.e., minimum density) covering of the plane with equal circles, solved by Kershner in 1939, can be interpreted as searching for the most economical distribution of transmission towers over a very large plane region, all towers having equal circular range, and collectively to provide reception at each point of the region. The problem of the thinnest 2-fold circle covering can be interpreted similarly, with the stronger requirement that the region should remain covered even if one of the towers stops functioning. Here we consider the intermediate variation, in which the region's coverage is to be maintained even if one of the towers experiences partial loss of power resulting in a certain decrease of its range radius. Specifically, we say that a covering of the plane with unit circular disks has margin µ (where 0 µ 1) if any one arbitrarily chosen disk can be replaced with a concentric disk of radius r = 1 - µ and the plane still remains covered. This concept provides a continuous transition from simple covering (margin 0) to 2-fold covering (margin 1). In this paper we determine the minimum density among all lattice circle coverings that have margin µ, and the lattice µ that produces the minimum density. Somewhat surprisingly, the optimal lattice µ behaves discontinuously and is non-unique at a pair of values of µ. As µ varies from 0 to 1, at one point µ changes suddenly from an equilateral triangular lattice into a square lattice and then, at another point, into a certain rectangular lattice.     

Dirac-type generalizations concerning large cycles in graphs

Bondy conjectured a common generalization of various results in hamiltonian graph theory concerning Hamilton and dominating cycles by introducing a notion of PD_λ-cycles (cycles that dominate all paths of lengths at least λ). We show that the minimum degree version of Bondy’s conjecture is true (along with the reverse version) if PD_λ-cycles are replaced by CD_λ-cycles (cycles that dominate all cycles of lengths at least λ). Fraisse proved a minimum degree generalization including a theorem of Nash-Williams for Hamilton cycles as a special case. We present the reverse version of this result including a theorem of Voss and Zuluaga as a special case. Two earlier less known results (due to the author) are crucial for the proofs of these results. All results are sharp in all respects. A number of possible similar generalizations are conjectured as well.     

最小度不小于3的图的圈长问题

Bondy和Vince曾证明最小度不小于3的图包含两个长度相差为1或者2的圈,这个结果回答了ErdSs提出的问题．Haggkvist和scott证明了除肠外,所有的3-正则图都包含两个长度相差2的圈．通过不同的方法,我们得到了下面的结论：除了每个端块都是硒的图外,所有最小度不小于3的图都包含两个长度相差2的圈．     

Mayberry-Murasugi's formula for links in homology 3-spheres

We prove the Mayberry-Murasugi formula for links in homology 3-spheres, which was proved before only for links in the 3-sphere. Our proof uses Franz-Reidemeister torsions.

     

Bounds for binary multiple covering codes

We study codes that are multiple coverings of the Hamming space and discuss lower and upper bounds onK(n, r, ), the minimum cardinality of a binary code of lengthn such that the Hamming spheres of radiusr centered at the codewords cover at least times. We also study the similar problem of multiple coverings containing repeated words. A table of bounds forn16,r4, 4 is given.     

Cycle-magic graphs

A simple graph G=(V,E) admits a cycle-covering if every edge in E belongs at least to one subgraph of G isomorphic to a given cycle C. Then the graph G is C-magic if there exists a total labelling f:V∪E→{1,2,…,|V|+|E|} such that, for every subgraph H^′=(V^′,E^′) of G isomorphic to C, ∑_v∈V^′f(v)+∑_e∈E^′f(e) is constant. When f(V)={1,…,|V|}, then G is said to be C-supermagic.We study the cyclic-magic and cyclic-supermagic behavior of several classes of connected graphs. We give several families of C_r-magic graphs for each r?3. The results rely on a technique of partitioning sets of integers with special properties.     

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.     

Coverings and Ring-Groupoids

We prove that the set of homotopy classes of the paths in a topological ring is a ring object (called ring groupoid). Using this concept we show that the ring structure of a topological ring lifts to a simply connected covering space.     

Revêtements modérés et groupe fondamenttal de graphe de groupes

Let R be a discrete complete valuation ring, with algebraically closedresidue field. Let X be a semi-stable R-curve, with smooth generic fibre. In this paper we study tame coverings of X.     

Bifurcations of limit cycles in a Z 4-equivariant quintic planar vector field

In this paper, a Z4-equivariant quintic planar vector field is studied. The Hopf bifurcation method and polycycle bifurcation method are combined to study the limit cycles bifurcated from the compounded cycle with 4 hyperbolic saddle points. It is found that this special quintic planar polynomial system has at least four large limit cycles which surround all singular points. By applying the double homoclinic loops bifurcation method and Hopf bifurcation method, we conclude that 28 limit cycles with two different configurations exist in this special planar polynomial system. The results acquired in this paper are useful for studying the weakened 16th Hilbert＇s Problem.     

Small Cycle Double Covers of Products II: Categorical and Strong Products with Paths and Cycles

We continue the study of small cycle double covers of products of graphs that began in [7], concentrating here on the categorical product and the strong product. Under the assumption that G has an SCDC, we show that G × P _m has an SCDC for all m ≠ 3, and that G × C _m has an SCDC for all m ≥ 3. For the strong product we use results about the categorical product and the Cartesian product [7] to show that if G has an SCDC, then so does G ⊠ C _m , m ≥ 5. Some results are also given for G ⊠ P _m , but require additional assumptions about the SCDC of G. The authors gratefully acknowledge the support of the Natural Sciences and Engineering Research Council of Canada.