Perfect codes in graphs

The classical problem of the existence of perfect codes is set in a vector space. In this paper it is shown that the natural setting for the problem is the class of distance-transitive graphs. A general theory is developed that leads to a simple criterion for the existence of a perfect code in a distance-transitive graph, and it is shown that this criterion implies Lloyd's theorem in the classical case.     

Perfect codes in the graphs Ok

In this paper we consider the existence of perfect codes in the infinite class of distance-transitive graphs O_k. Perfect 1-codes correspond to certain Steiner systems and necessary conditions for the existence of such a code are satisfied if k + 1 is prime. We give some nonexistence results for perfect 2-, 3-, and 4-codes and for perfect e-codes in general, including a lower bound for k in terms of e.     

Perfect k-line graphs and k-total graphs

The concept of the line graph can be generalized as follows. The k-line graph L_k(G) of a graph G is defined as a graph whose vertices are the complete subgraphs on k vertices in G. Two distinct such complete subgraphs are adjacent in L_k(G) if and only if they have in G k ? 1 vertices in common. The concept of the total graph can be generalized similarly. Then the Perfect Graph Conjecture will be proved for 3-line graphs and 3-total graphs. Moreover, perfect 3-line graphs are not contained in any of the known classes of perfect graphs. © 1993 John Wiley & Sons, Inc.     

Perfect couples of graphs

We generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graphG with a probability distributionP on its vertex set. For any fixedP it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those ofG and its complement G iffG is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.The research of the authors is partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant No. 1806 resp. No. 1812.     

Perfect graphs and norms

For a given undirected graphG=(V, ) withn vertices we define four norms on ⁿ , namely, where (resp.) stands for the family of all maximal cliques inG (resp. , the complement ofG). The goal of this note is to demonstrate the usefulness of some notions and techniques from functional analysis in graph theory by showing how Theorem 2.1 (G is -perfect if and only if the norms are equal) together with the reflexivity of the space ⁿ equipped with either of the norms above easily yield one new result (Theorem 2.2) and two known characterizations of perfect graphs (Theorems 2.3–2.4). Namely, Theorem 2.2 provides a characterization of -perfection that is strongly related to that of Lovász (1972). It implies that the Lovász inequality is exactly the classical Schwartz inequality for the space ( ⁿ , ·) restricted to (0, 1) vectorsx, y satisfyingx = y. Theorem 2.3 is well known as the Perfect Graph Theorem, while Theorem 2.4, due to V. Chvátal and D.R. Fulkerson, characterizes -perfection of a graphG in terms of the equality between the vertex packing polytope ofG and the fractional vertex packing polytope ofG.     

Neighbour-transitive codes in Johnson graphs

The Johnson graph \(J(v,k)\) has, as vertices, the \(k\) -subsets of a \(v\) -set \(\mathcal {V}\) and as edges the pairs of \(k\) -subsets with intersection of size \(k-1\) . We introduce the notion of a neighbour-transitive code in \(J(v,k)\) . This is a proper vertex subset \(\Gamma \) such that the subgroup \(G\) of graph automorphisms leaving \(\Gamma \) invariant is transitive on both the set \(\Gamma \) of ‘codewords’ and also the set of ‘neighbours’ of \(\Gamma \) , which are the non-codewords joined by an edge to some codeword. We classify all examples where the group \(G\) is a subgroup of the symmetric group \(\mathrm{Sym}\,(\mathcal {V})\) and is intransitive or imprimitive on the underlying \(v\) -set \(\mathcal {V}\) . In the remaining case where \(G\le \mathrm{Sym}\,(\mathcal {V})\) and \(G\) is primitive on \(\mathcal {V}\) , we prove that, provided distinct codewords are at distance at least \(3\) , then \(G\) is \(2\) -transitive on \(\mathcal {V}\) . We examine many of the infinite families of finite \(2\) -transitive permutation groups and construct surprisingly rich families of examples of neighbour-transitive codes. A major unresolved case remains.     

Perfect codes as isomorphic spaces

Linear equivalence between perfect codes is defined. This definition gives the concept of general perfect 1-error correcting binary codes. These are defined as 1-error correcting perfect binary codes, with the difference that the set of errors is not the set of weight one words, instead any set with cardinality n and full rank is allowed. The side class structure defines the restrictions on the subspace of any general 1-error correcting perfect binary code. Every linear equivalence class will contain all codes with the same length, rank and dimension of kernel and all codes in the linear equivalence class will have isomorphic side class structures.     

Perfect state transfer in cubelike graphs

Suppose C is a subset of non-zero vectors from the vector space . The cubelike graphX(C) has as its vertex set, and two elements of are adjacent if their difference is in C. If M is the d×|C| matrix with the elements of C as its columns, we call the row space of M the code of X. We use this code to study perfect state transfer on cubelike graphs. Bernasconi et al. have shown that perfect state transfer occurs on X(C) at time π/2 if and only if the sum of the elements of C is not zero. Here we consider what happens when this sum is zero. We prove that if perfect state transfer occurs on a cubelike graph, then it must take place at time τ=π/2D, where D is the greatest common divisor of the weights of the code words. We show that perfect state transfer occurs at time π/4 if and only if D=2 and the code is self-orthogonal.     

Perfect matchings in pruned grid graphs

We determine conditions sufficient to guarantee the existence of a perfect matching when vertices are removed from finite and infinite grid graphs. The conditions impose a minimum distance between the vertices that are removed. While the distances are likely not best possible, they are best possible with respect to asymptotic growth rate.     

Perfect matchings in regular bipartite graphs

P. Hall, [2], gave necessary and sufficient conditions for a bipartite graph to have a perfect matching. Koning, [3], proved that such a graph can be decomposed intok edge-disjoint perfect matchings if and only if it isk-regular. It immediately follows that in ak-regular bipartite graphG, the deletion of any setS of at mostk – 1 edges leaves intact one of those perfect matchings. However, it is not known what happens if we delete more thank – 1 edges. In this paper we give sufficient conditions so that by deleting a setS ofk + r edgesr 0, stillG – S has a perfect matching. Furthermore we prove that our result, in some sense, is best possible.     

Perfect matchings in random intersection graphs

Let W ₁,??,W _n be independent random subsets of [m]={1,??,m}. Assuming that each W _i is uniformly distributed in the class of d-subsets of?[m] we study the uniform random intersection graph G _s (n,m,d) on the vertex set {W ₁,??W _n }, defined by the adjacency relation: W _i ??W _j whenever |W _i ??W _j |?Rs. For even?n we show that as n,m???? the edge density threshold for the property that G _s (n,m,d) contains a perfect matching is asymptotically the same as that for G _s (n,m,d) being connected.     

Nearly perfect codes in distance-regular graphs

The idea of a nearly perfect code in a vector space over a binary field is generalized to the class of distance-regular graphs. A necessary condition for the existence of a nearly perfect code in a distance-regular graph is obtained, and it is shown that this condition implies the analogous result in the classical binary case.     

Sporadic neighbour-transitive codes in Johnson graphs

We classify the neighbour-transitive codes in Johnson graphs $J(v,k)$ of minimum distance at least three which admit a neighbour-transitive group of automorphisms that is an almost simple two-transitive group of degree $v$ and does not occur in an infinite family of two-transitive groups. The result of this classification is a table of 22 codes with these properties. Many have relatively large minimum distance in comparison to their length $v$ and number of code words. We construct an additional five neighbour-transitive codes with minimum distance two admitting such a group. All 27 codes are $t$ -designs with $t$ at least two.     

Gray codes in graphs of subsets

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of “O's” and “1's” with k “1's”. Two such subsets are adjacent if one can be obtained from the other by switching a “O” and a “1” which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding “Gray codes” of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n?7 and that such a cycle does exist in all other cases where k?5.