Perfect divisibility and 2-divisibility

A graph G is said to be 2-divisible if for all (nonempty) induced subgraphs H of G, can be partitioned into two sets such that and . (Here denotes the clique number of G, the number of vertices in a largest clique of G). A graph G is said to be perfectly divisible if for all induced subgraphs H of G, can be partitioned into two sets such that is perfect and . We prove that if a graph is -free, then it is 2-divisible. We also prove that if a graph is bull-free and either odd-hole-free or P₅-free, then it is perfectly divisible.     

Perfect 3-colorings on 6-regular graphs of order 9

The concept of a perfect coloring, introduced by P. Delsarte, generalizes the concept of completely regular code. We study the perfect 3-colorings (also known as the equitable partitions into three parts) on 6-regular graphs of order 9. A perfect n-colorings of a graph is a partition of its vertex set. It splits vertices into n parts A1, A2,...,An such that for all i,j∈{1,2,...,n}, each vertex of Ai is adjacent to aij vertices of Aj. The matrix A =(aij)n×n is called quotient matrix or parameter matrix. In this article, we start by giving an algorithm to find all different types of 6-regular graphs of order 9. Then, we classify all the realizable parameter matrices of perfect 3-colorings on 6-regular graphs of order 9.     

Switching Equivalence Classes of Perfect Codes

The authors present a 1-error correcting perfect code of length 15 and show that it is not switching equivalent to the Hamming code thereby settling a question of Avgustinovich and Solov'evaas96     

On Perfect Ternary Constant Weight Codes

We consider the space of ternary words of length n and fixed weight w with the usual Hamming distance. A sequence of perfect single error correcting codes in this space is constructed. We prove the nonexistence of such codes with other parameters than those of the sequence.     

On Perfect 2‐Colorings of Johnson Graphs J(v, 3)

We study the perfect 2‐colorings (also known as the equitable partitions into two parts or the completely regular codes with covering radius 1) of the Johnson graphs . In particular, we classify all the realizable quotient matrices of perfect 2‐colorings for odd v. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 232–252, 2013     

Linear Perfect Codes and a Characterization of the Classical Designs

A new definition for the dimension of a combinatorial t-(v,k,) design over a finite field is proposed. The complementary designs of the hyperplanes in a finite projective or affine geometry, and the finite Desarguesian planes in particular, are characterized as the unique (up to isomorphism) designs with the given parameters and minimum dimension. This generalizes a well-known characterization of the binary hyperplane designs in terms of their minimum 2-rank. The proof utilizes the q-ary analogue of the Hamming code, and a group-theoretic characterization of the classical designs.     

On 3-colorings of Plane Graphs

In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G. This gives a positive support to a conjecture of Borodin and Raspaud which claims that each plane graph without 5-circuits and intersecting triangles is 3-colorable.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$     

Perfect cliques and colorings of Polish spaces

A coloring of a set is any subset of , where 1$"> is a natural number. We give some sufficient conditions for the existence of a perfect -homogeneous set, in the case where is and is a Polish space. In particular, we show that it is sufficient that there exist -homogeneous sets of arbitrarily large countable Cantor-Bendixson rank. We apply our methods to show that an analytic subset of the plane contains a perfect -clique if it contains any uncountable -clique, where is a natural number or (a set is a -clique in if the convex hull of any of its -element subsets is not contained in ).

     

New i‐Perfect Cycle Decompositions via Vertex Colorings of Graphs

Generalizing a result by Buratti et al.[M. Buratti, F. Rania, and F. Zuanni, Some constructions for cyclic perfect cycle systems, Discrete Math 299 (2005), 33–48], we present a construction for i‐perfect k‐cycle decompositions of the complete m‐partite graph with parts of size k. These decompositions are sharply vertex‐transitive under the additive group of with R a suitable ring of order m. The construction works whenever a suitable i‐perfect map exists. We show that for determining the set of all triples for which such a map exists, it is crucial to calculate the chromatic numbers of some auxiliary graphs. We completely determine this set except for one special case where is the product of two distinct primes, is even, and . This result allows us to obtain a plethora of new i‐perfect k‐cycle decompositions of the complete graph of order (mod 2k) with k odd. In particular, if k is a prime, such a decomposition exists for any possible i provided that .     

Existence of Perfect 3-Deletion-Correcting Codes

Bours [4] recently showed some constructions for perfect 2 and 3-deletion-correcting codes from combinatorial designs. He settled existence of perfect 2-deletion-correcting codes with words of length 4. However, the existence of perfect 3-deletion-correcting codes with words of length 5, or T^*(2, 5, v), remained unsettled for v 7, 8 (mod 10) and v = 13, 14, 15, 16. In this paper we provide new constructions for these codes from combinatorial designs, and show that a T^*(2, 5, v) exists for all v.     

Transitivity of varietal hypercube networks

The varietal hypercube VQn is a variant of the hypercube Qn and has better properties than Qn with the same number of edges and vertices. This paper proves that VQn is vertex-transitive. This property shows that when VQn is used to model an interconnection network, it is high symmetrical and obviously superior to other variants of the hypercube such as the crossed cube.     

Two-dimensional minimax Latin hypercube designs

We investigate minimax Latin hypercube designs in two dimensions for several distance measures. For the ?^∞-distance we are able to construct minimax Latin hypercube designs of n points, and to determine the minimal covering radius, for all n. For the ?¹-distance we have a lower bound for the covering radius, and a construction of minimax Latin hypercube designs for (infinitely) many values of n. We conjecture that the obtained lower bound is attained, except for a few small (known) values of n. For the ?²-distance we have generated minimax solutions up to n=27 by an exhaustive search method. The latter Latin hypercube designs are included in the website www.spacefillingdesigns.nl.     

Slightly subcritical hypercube percolation

We study bond percolation on the hypercube {0,1}^m in the slightly subcritical regime where p = p_c(1 ? ε_m) and ε_m = o(1) but ε_m ? 2^?m/3 and study the clusters of largest volume and diameter. We establish that with high probability the largest component has cardinality , that the maximal diameter of all clusters is , and that the maximal mixing time of all clusters is . These results hold in different levels of generality, and in particular, some of the estimates hold for various classes of graphs such as high‐dimensional tori, expanders of high degree and girth, products of complete graphs, and infinite lattices in high dimensions.     

The diameter of a random subgraph of the hypercube

In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work, the inequalities n + m_p ≤ D(G_n) ≤ n + m_p + 8 almost surely hold as n → ∞, where n is dimension of the hypercube and m_p depends only on sampling probabilities. It is not clear from their work, whether the values of the diameter are really distributed on these 9 values, or whether the inequality can be sharpened. In this paper we introduce several new ideas, using which we are able to obtain an exact result: D(G_n) = n + m_p (almost surely). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Graphs with full rank 3-color matrix and few 3-colorings

We exhibit a counterexample to a conjecture of Thomassen stating that the number of distinct 3-colorings of every graph whose 3-color matrix has full column rank is superpolynomial in the number of vertices.