Coverings of the Vertices of a Graph by Small Cycles

Given a graph G with n vertices, we call c_k(G) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G. We bound c_k(G) from the minimum degree and the order of the graph.     

Coverings by minimal transversals

In this paper, we give counterexamples to the conjecture: “Every nonempty regular simple graph contains two disjoint maximal independent sets” [2, 7]. For this, we generalize this problem to the following: covering the set of vertices of a graph by minimal transversals. An equivalence of this last problem is given.     

Coverings by open cells

We prove that in a semi-bounded o-minimal expansion of an ordered group every non-empty open definable set is a finite union of open cells.     

Resolvable Representation of Polyhedra

The paper proposes a new method for the boundary representation of three-dimensional (not necessarily convex) polyhedra, called a resolvable representation , in which small numerical errors do not violate the symbolic part of the representation. In this representation, numerical data are represented partly by the coordinates of vertices and partly by the coefficients of face equations in such a way that the polyhedron can be reconstructed from the representation in a step-by-step manner. It is proved that any polyhedron homeomorphic to a sphere has a resolvable representation, and an algorithm for finding such a representation is constructed. Received January 21, 1997, and in revised form April 29, 1998.     

Minimal 2-Fold Coverings of E d

Let N(k, d) be the smallest positive integer such that given any finite collection of open halfspaces which k-fold coversE ^d , there exists a subcollection of cardinality less than or equal toN(k,d) which k-fold coversE ^d . A well-known corollary to Helly's theorem proves N(1,d) =d+1. This provides an inductive base from which we show N(k; d) exists for all positive integers k.Our main result is .     

Coverings by classes of permutable equivalence relations

Supported by the Russian Foundation for Fundamental Research, grant No. 93-01-16011.     

Enlargements and Coverings by Rees Matrix Semigroups

 We formulate a general condition, called an enlargement, under which a semigroup T is covered by a Rees matrix semigroup over a subsemigroup. (Received 1 February 1999; in revised form 19 May 1999)     

Resolvable path designs

A resolvable (balanced) path design, RBPD(v, k, λ) is the decomposition of λ copies of the complete graph on v vertices into edge-disjoint subgraphs such that each subgraph consists of $\text{v}\text{k}$ vertex-disjoint paths of length k ? 1 (k vertices). It is shown that an RBPD(v, 3, λ) exists if and only if v ≡ 9 (modulo 12/gcd(4, λ)). Moreover, the RBPD(v, 3, λ) can have an automorphism of order $\text{v}\text{3}$. For k > 3, it is shown that if v is large enough, then an RBPD(v, k, 1) exists if and only if v ≡ k² (modulo lcm(2k ? 2, k)). Also, it is shown that the categorical product of a k-factorable graph and a regular graph is also k-factorable. These results are stronger than two conjectures of P. Hell and A. Rosa     

On Perfect Matching Coverings and Even Subgraph Coverings

A perfect matching covering of a graph G is a set of perfect matchings of G such that every edge of G is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph admits a perfect matching covering of order at most 5 (we call such a collection of perfect matchings a Berge covering of G). A cubic graph G is called a Kotzig graph if G has a 3‐edge‐coloring such that each pair of colors forms a hamiltonian circuit (introduced by R. Häggkvist, K. Markström, J Combin Theory Ser B 96 (2006), 183–206). In this article, we prove that if there is a vertex w of a cubic graph G such that , the graph obtained from by suppressing all degree two vertices is a Kotzig graph, then G has a Berge covering. We also obtain some results concerning the so‐called 5‐even subgraph double cover conjecture.     

On Resolvable Multipartite G-Designs II

In this paper, it has been proved that and are factorable, where ⊗ denotes wreath product of graphs. As a consequence, a resolvable (k,n,k,2λ) multipartite –design exists for even k. These results generalize the results of Ushio on –factorizations of complete tripartite graphs.     

Enlargements and Coverings by Rees Matrix Semigroups

 We formulate a general condition, called an enlargement, under which a semigroup T is covered by a Rees matrix semigroup over a subsemigroup.     

Coverings by convex bodies and inscribed balls

Let be a Hilbert space. For a closed convex body denote by the supremum of the radiuses of balls contained in . We prove that for every covering of a convex closed body by a sequence of convex closed bodies , . It looks like this fact is new even for triangles in a 2-dimensional space.

     

Holomorphic L2 Functions on Coverings of Pseudoconvex Manifolds

((Without abstract)) Submitted: May 1997     

Orthogonally Resolvable Cycle Decompositions

If a cycle decomposition of a graph G admits two resolutions, and , such that for each resolution class and , then the resolutions and are said to be orthogonal. In this paper, we introduce the notion of an orthogonally resolvable cycle decomposition, which is a cycle decomposition admitting a pair of orthogonal resolutions. An orthogonally resolvable cycle decomposition of a graph G may be represented by a square array in which each cell is either empty or filled with a k–cycle from G, such that every vertex appears exactly once in each row and column of the array and every edge of G appears in exactly one cycle. We focus mainly on orthogonal k‐cycle decompositions of and (the complete graph with the edges of a 1‐factor removed), denoted . We give general constructions for such decompositions, which we use to construct several infinite families. We find necessary and sufficient conditions for the existence of an OCD(n, 4). In addition, we consider orthogonal cycle decompositions of the lexicographic product of a complete graph or cycle with . Finally, we give some nonexistence results.     

关于格点覆盖的一个注记

对于一个给定椭球,本文给出了它的任一全等椭球都包含一个整点的一个充分必要条件.     

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.