Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

On the minimum average distance of binary constant weight codes

Let β(n,M,w) denote the minimum average Hamming distance of a binary constant weight code with length n, size M and weight w. In this paper, we study the problem of determining β(n,M,w). Using the methods from coding theory and linear programming, we derive several lower bounds on the average Hamming distance of a binary constant weight code. These lower bounds enable us to determine the exact value for β(n,M,w) in several cases.     

Strict L<Subscript>∞</Subscript> Isotonic Regression

Given a function f and weights w on the vertices of a directed acyclic graph G, an isotonic regression of (f,w) is an order-preserving real-valued function that minimizes the weighted distance to f among all order-preserving functions. When the distance is given via the supremum norm there may be many isotonic regressions. One of special interest is the strict isotonic regression, which is the limit of p-norm isotonic regression as p approaches infinity. Algorithms for determining it are given. We also examine previous isotonic regression algorithms in terms of their behavior as mappings from weighted functions over G to isotonic functions over G, showing that the fastest algorithms are not monotonic mappings. In contrast, the strict isotonic regression is monotonic.     

On a multiplication and a theory of integration for belief and plausibility functions

Belief and plausibility functions have been introduced as generalizations of probability measures, which abandon the axiom of additivity. It turns out that elementwise multiplication is a binary operation on the set of belief functions. If the set functions of the type considered here are defined on a locally compact and separable space X, a theorem by Choquet ensures that they can be represented by a probability measure on the space containing the closed subsets of X, the so-called basic probability assignment. This is basic for defining two new types of integrals. One of them may be used to measure the degree of non-additivity of the belief or plausibility function. The other one is a generalization of the Lebesgue integral. The latter is compared with Choquet's and Sugeno's integrals for non-additive set functions.     

Quasi-median hulls in Hamming space are Steiner hulls

A Hamming space Λⁿ consists of all sequences of length n over an alphabet Λ and is endowed with the Hamming distance. In particular, any set of aligned DNA sequences of fixed length constitutes a subspace of a Hamming space with respect to mismatch distance. The quasi-median operation returns for any three sequences u,v,w the sequence which in each coordinate attains either the majority coordinate from u,v,w or else (in the case of a tie) the coordinate of the first entry, u; for a subset of Λⁿ the iterative application of this operation stabilizes in its quasi-median hull. We show that for every finite tree interconnecting a given subset X of Λⁿ there exists a shortest realization within Λⁿ for which all interior nodes belong to the quasi-median hull of X. Hence the quasi-median hull serves as a Steiner hull for the Steiner problem in Hamming space.     

Analog of <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> with a subadditive measure

For a subadditive fuzzy measure (not assumed finite), a Minkowski type triangle inequality, with Choquet integrals in place of Lebesgue integrals, is shown to hold. It is immediate that the set of functions for which a certain positive power of the absolute values have finite Choquet integrals is closed under addition, leading to a linear space analogous to the Lebesgue space L ^p , with a metric related to the integral of that power. Under the additional condition that the subadditive fuzzy measure is inner continuous (Sugeno), the space is shown to be complete. Consequences of the Minkowski type inequality are illustrated in two specific instances.      

The representations of two types of functionals on L∞(Ω, ?) and L∞(Ω, ?, ?)

This article gives the representations of two types of real functionals on L ^∞(Ω, Ƒ) or L ^∞(Ω, Ƒ, ℙ) in terms of Choquet integrals. These functionals are comonotonically subadditive and comonotonically convex, respectively.     

NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF CLAW-FREE GRAPHS

Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)＞n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too.     

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.     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

Construction of Constant GC-Content DNA Codes via a Variable Neighbourhood Search Algorithm

DNA codes are sets of words of fixed length n over the alphabet {A,C,G,T} which satisfy a number of combinatorial conditions. They have application in DNA computing, in DNA microarray technologies and as molecular bar codes. The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. In this paper the construction of DNA codes is studied from an algorithmic perspective. Four local search algorithms are developed and combined in a variable neighbourhood search framework. The algorithm has been run extensively. Over 254 problems considered, it was able to match or improve the best known lower bounds in 180 cases, with 52 new bests.      

Almost invariant submanifolds for compact group actions

We define a C ¹ distance between submanifolds of a riemannian manifold M and show that, if a compact submanifold N is not moved too much under the isometric action of a compact group G, there is a G-invariant submanifold C ¹-close to N. The proof involves a procedure of averaging nearby submanifolds of riemannian manifolds in a symmetric way. The procedure combines averaging techniques of Cartan, Grove/Karcher, and de la Harpe/Karoubi with Whitney’s idea of realizing submanifolds as zeros of sections of extended normal bundles. Received September 14, 1999 / final version received November 29, 1999     

On Certain Weak Engel-Type Conditions in Groups

Let w(x, y) be a word in two variables and 𝔚 the variety determined by w. In this paper we raise the following question: if for every pair of elements a, b in a group G there exists g ∈ G such that w(a ^g , b) = 1, under what conditions does the group G belong to 𝔚? In particular, we consider the n-Engel word w(x, y) = [x, _n y]. We show that in this case the property is satisfied when the group G is metabelian. If n = 2, then we extend this result to the class of all solvable groups.     

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

Equitable list coloring and treewidth

Given lists of available colors assigned to the vertices of a graph G, a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k, then a list coloring is equitable if each color appears on at most ?|V(G)|/k? vertices. A graph is equitably k ‐choosable if such a coloring exists whenever the lists all have size k. Kostochka, Pelsmajer, and West introduced this notion and conjectured that G is equitably k‐choosable for k>Δ(G). We prove this for graphs of treewidth w≤5 if also k≥3w?1. We also show that if G has treewidth w≥5, then G is equitably k‐choosable for k≥max{Δ(G)+w?4, 3w?1}. As a corollary, if G is chordal, then G is equitably k‐choosable for k≥3Δ(G)?4 when Δ(G)>2. © 2009 Wiley Periodicals, Inc. J Graph Theory     

Non-Bicritical Critical Snarks

 Snarks are cubic graphs with chromatic index χ^′=4. A snark G is called critical if χ^′ (G−{v,w})=3 for any two adjacent vertices v and w, and it is called bicritical if χ^′ (G−{v,w})=3 for any two vertices v and w. We construct infinite families of critical snarks which are not bicritical. This solves a problem stated by Nedela and Škoviera. Revised: January 11, 1999     

Structure of principal eigenvectors and genetic diversity

The main concern of this paper is long-term genotypic diversity. Genotypes are represented as finite sequences (s₁,s₂,…,s_n), where the entries {s_i} are drawn from a finite alphabet. The mutation matrix is given in terms of Hamming distances. It is proved that the long time behavior of solutions for a class of genotype evolution models is governed by the principal eigenvectors of the sum of the mutation and fitness matrices. It is proved that the components of principal eigenvectors are symmetric and monotonely decreasing in terms of Hamming distances whenever the fitness matrix has those properties.     

An optimal greedy routing algorithm for triangulated polygons

In this paper, we prove that a triangulated polygon G admits a greedy embedding into an appropriate semi-metric space such that using an appropriate distance definition, for any two vertices u and w in G, a most virtual distance decreasing path is always a minimum-edge path between u and w. Therefore, our greedy routing algorithm is optimal. The greedy embedding of G can be obtained in linear time. To the best of our knowledge, this is the first optimal greedy routing algorithm for a nontrivial subcategory of graphs.