Dense sets and embedding binary trees into hypercubes

The purpose of this paper is to describe a method for embedding binary trees into hypercubes based on an iterative embedding into their subgraphs induced by dense sets. As a particular application, we present a class of binary trees, defined in terms of size of their subtrees, whose members allow a dilation two embedding into their optimal hypercubes. This provides a partial evidence in favor of a long-standing conjecture of Bhatt and Ipsen which claims that such an embedding exists for an arbitrary binary tree.     

The representation number of some sparse graphs

We study the representation number for some special sparse graphs. For graphs with a single edge and for complete binary trees we give an exact formula, and for hypercubes we improve the known lower bound. We also study the prime factorization of the representation number of graphs with one edge.     

Spherical and Clockwise Spherical Graphs

The main subject of our study are spherical (weakly spherical) graphs, i.e. connected graphs fulfilling the condition that in each interval to each vertex there is exactly one (at least one, respectively) antipodal vertex. Our analysis concerns properties of these graphs especially in connection with convexity and also with hypercube graphs. We deal e.g. with the problem under what conditions all intervals of a spherical graph induce hypercubes and find a new characterization of hypercubes: G is a hypercube if and only if G is spherical and bipartite.     

超立方体Q_n的传递剖分

一个图的传递剖分是它的边集的一个划分,且满足图的一个自同构群在其划分后的各个部分组成的集合上作用是传递的.决定了超立方体Q_n的所有G-传递剖分,其中G为Q_n的全自同构群.     

On the spanning tree packing number of a graph: a survey

The spanning tree packing number or STP number of a graph G is the maximum number of edge-disjoint spanning trees contained in G. We use an observation of Paul Catlin to investigate the STP numbers of several families of graphs including quasi-random graphs, regular graphs, complete bipartite graphs, cartesian products and the hypercubes.     

立方体网络路由选择算法

本文利用图论理论 ,基于路由选择能力的概念 ,建立了一个有效的路由选择算法 ,该算法可以在含有节点故障和边故障的容错超立方体上使用 ,且具有较强的容错性 .     

Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets

This paper studies techniques of finding hamiltonian paths and cycles in hypercubes and dense sets of hypercubes. This problem is, in general, easily solvable but here the problem was modified by the requirement that a set of edges has to be used in such path or cycle. The main result of this paper says that for a given n, any sufficiently large hypercube contains a hamiltonian path or cycle with prescribed n edges just when the family of the edges satisfies certain natural necessary conditions. Analogous results are presented for dense sets. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Decycling graphs

In this paper, we introduce the decycling number of a graph as the minimum number of vertices that must be removed in order to eliminate all cycles. After proving some general results, we focus on two families of graph products, the grids and the hypercubes. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 59–77, 1997     

The carving-width of generalized hypercubes

The carving-width of a graph is the minimum congestion of routing trees for the graph. We determine the carving-width of generalized hypercubes: Hamming graphs, even grids, and tori. Our results extend the result of Chandran and Kavitha [L.S. Chandran, T. Kavitha, The carvingwidth of hypercubes, Discrete Math. 306 (2006) 2270-2274] that determines the carving-width of hypercubes.     

A Note on the Construction of Orthogonal Latin Hypercube Designs

Latin hypercube designs have been found very useful for designing computer experiments. In recent years, several methods of constructing orthogonal Latin hypercube designs have been proposed in the literature. In this article, we report some more results on the construction of orthogonal Latin hypercubes which result in several new designs.     

Transversals in completely reducible multiary quasigroups and in multiary quasigroups of order 4

An $n$-ary quasigroup $f$ of order $q$ is an $n$-ary operation over a set of cardinality $q$ such that the Cayley table of the operation is an $n$-dimensional latin hypercube of order $q$. A transversal in a quasigroup $f$ (or in the corresponding latin hypercube) is a collection of $q$$(n+1)$-tuples from the Cayley table of $f$, each pair of tuples differing at each position. The problem of transversals in latin hypercubes was posed by Wanless in 2011.An $n$-ary quasigroup $f$ is called reducible if it can be obtained as a composition of two quasigroups whose arity is at least 2, and it is completely reducible if it can be decomposed into binary quasigroups.In this paper we investigate transversals in reducible quasigroups and in quasigroups of order 4. We find a lower bound on the number of transversals for a vast class of completely reducible quasigroups. Next we prove that, except for the iterated group ${\mathbb{Z}}_4$ of even arity, every $n$-ary quasigroup of order 4 has a transversal. Also we obtain a lower bound on the number of transversals in quasigroups of order 4 and odd arity and count transversals in the iterated group ${\mathbb{Z}}_4$ of odd arity and in the iterated group ${\mathbb{Z}}_2^2.$All results of this paper can be regarded as those concerning latin hypercubes.     

完全二叉树的量词消去

量词消去法已经成为计算机科学和代数模型论中最有力的研究工具之一.本 文针对完全二叉树理论所独有的特性,给出了它的基本公式集,然后利用分布公式及 有限覆盖证明了完全二叉树的理论可以量词消去.     

Equiorthogonal Frequency Hypercubes: Preliminary Theory

Using a strong definition of frequency hypercube, we define a strengthened form of orthogonality, called equiorthogonality, for sets of such hypercubes. We prove that the maximum possible number of mutually equiorthogonal frequency hypercubes (MEFH) of order n and dimension d based on m distinct symbols is (n-1)^d/(m-1). A set of (n-1)^d/(m-1) such MEFH is called a complete set. Because of the stronger conditions on the hypercubes, we can find complete sets of MEFH of all lower dimensions within any complete set of MEFH; this useful property is not shared by sets of mutually orthogonal hypercubes using the usual, weaker definition.     

Complete Sets of Mutually Orthogonal Hypercubes and Their Connections to Affine Resolvable Designs

. Recently, Laywine and Mullen proved several generalizations of Bose's equivalence between the existence of complete sets of mutually orthogonal Latin squares of order n and the existence of affine planes of order n. Laywine further investigated the relationship between sets of orthogonal frequency squares and affine resolvable balanced incomplete block designs. In this paper we generalize several of Laywine's results that were derived for frequency squares. We provide sufficient conditions for construction of an affine resolvable design from a complete set of mutually orthogonal Youden frequency hypercubes; we also show that, starting with a complete set of mutually equiorthogonal frequency hypercubes, an analogous construction can always be done. In addition, we give conditions under which an affine resolvable design can be converted to a complete set of mutually orthogonal Youden frequency hypercubes or a complete set of mutually equiorthogonal frequency hypercubes.     

Properties of complete sets of mutually equiorthogonal frequency hypercubes

A complete set of mutually equiorthogonal frequency hypercubes (MEFH) of ordern and dimensiond, usingm distinct symbols, has (n−1) ^d /(m−1) hypercubes. In this article, we explore the properties of complete sets of MEFH. As a consequence of these properties, we show that existence of such a set implies that the number of symbolsm is a prime power. We also establish an equivalence between existence of a complete set of MEFH and existence of a certain complete set of Latin hypercubes and a certain complete orthogonal array.     

Approximate inference in Bayesian networks using binary probability trees

The present paper introduces a new kind of representation for the potentials in a Bayesian network: Binary Probability Trees. They enable the representation of context-specific independences in more detail than probability trees. This enhanced capability leads to more efficient inference algorithms for some types of Bayesian networks. This paper explains the procedure for building a binary probability tree from a given potential, which is similar to the one employed for building standard probability trees. It also offers a way of pruning a binary tree in order to reduce its size. This allows us to obtain exact or approximate results in inference depending on an input threshold. This paper also provides detailed algorithms for performing the basic operations on potentials (restriction, combination and marginalization) directly to binary trees. Finally, some experiments are described where binary trees are used with the variable elimination algorithm to compare the performance with that obtained for standard probability trees.     

Une involution sur les chemins de Dyck

We give a bijection between some valuated complete binary trees according to the number of leaves and multichains on a partially ordered set.     

An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions

In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the subproblem is solved by Barzilai–Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time.     

A note on the cubical dimension of new classes of binary trees

The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 ⁿ vertices, n ? 1, is n. The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.     

On the dimension of affine resolvable designs and hypercubes

The equivalence between complete sets of mutually orthogonal hypercubes and affine resolvable designs, which generalizes the well-known equivalence between complete sets of mutually orthogonal latin squares and affine planes, is used to examine the dimension of designs by studying the prime classes in the associated hypercubes. Particular attention is given to designs of order n=9 including a design which is nonisomorphic to AG(3, 9) even though it possesses the same parameters and three prime classes. © 1996 John Wiley & Sons, Inc.