Minimum average congestion of enhanced and augmented hypercubes into complete binary trees

We study the embedding problem of enhanced and augmented hypercubes into complete binary trees. Using tree traversal techniques, we compute the minimum average edge congestion of enhanced and augmented hypercubes into complete binary trees.     

On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

在曲面上图嵌入的唯一性(英)

在本文中，证明了图嵌入在一个已知曲面上的唯一性充分条件．这个条件比［4］中要弱些．     

The cubicity of hypercube graphs

For a graph G, its cubicity is the minimum dimension k such that G is representable as the intersection graph of (axis-parallel) cubes in k-dimensional space. (A k-dimensional cube is a Cartesian product R₁×R₂×?×R_k, where R_i is a closed interval of the form [a_i,a_i+1] on the real line.) Chandran et al. [L.S. Chandran, C. Mannino, G. Oriolo, On the cubicity of certain graphs, Information Processing Letters 94 (2005) 113-118] showed that for a d-dimensional hypercube H_d, . In this paper, we use the probabilistic method to show that . The parameter boxicity generalizes cubicity: the boxicity of a graph G is defined as the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes in k-dimensional space. Since for any graph G, our result implies that . The problem of determining a non-trivial lower bound for is left open.     

Decomposing the hypercube Qn into n isomorphic edge-disjoint trees

We show that the edge set of the $n$-dimensional hypercube $Q_n$ is the disjoint union of the edge sets of $n$ isomorphic trees.     

Monotonicity of the minimum cardinality of an identifying code in the hypercube

Let M_t(n) denote the minimum cardinality of a t-identifying code in the n-cube. It was conjectured that for all n?2 and t?1 we have M_t(n)?M_t(n+1). We prove this inequality for t=1.     

Embedding 5-cycle systems into pentagon triple systems

We show that the spectrum for pentagon triple systems is the set of all n≡1,15,21 or . We then construct a 5-cycle system of order 10n+1 which can be embedded in a pentagon triple system of order 30n+1 and also construct a 5-cycle system of order 10n+5 which can be embedded in a pentagon triple system of order 30n+15, with the possible exception of embedding a 5-cycle system of order 21 in a pentagon triple system of order 61.     

On even-cycle-free subgraphs of the hypercube

It is shown that the size of any C4k+2-free subgraph of the hypercube Qn, k?3, is o(e(Qn)).     

None of the coronoid systems can be isometrically embedded into a hypercube

A graph that can be isometrically embedded into a hypercube is called a partial cube (or binary Hamming graph). Klavžar, Gutman and Mohar [S. Klavžar, I. Gutman, B. Mohar, Labeling of benzenoid systems which reflects the vertex-distance relations, J. Chem. Inf. Comput. Sci. 35 (1995) 590–593] showed that all benzenoid systems are partial cubes. In this article we show that none of the coronoid systems (benzenoid systems with “holes”) is a partial cube.     

Exact hyperplane covers for subsets of the hypercube

Alon and Füredi (1993) showed that the number of hyperplanes required to cover ${\{0,1\}}^n?\{0\}$ without covering 0 is n. We initiate the study of such exact hyperplane covers of the hypercube for other subsets of the hypercube. In particular, we provide exact solutions for covering ${\{0,1\}}^n$ while missing up to four points and give asymptotic bounds in the general case. Several interesting questions are left open.     

Embedding the bicyclic semigroup into countably compact topological semigroups

We study algebraic and topological properties of topological semigroups containing a copy of the bicyclic semigroup C(p,q). We prove that a topological semigroup S with pseudocompact square contains no dense copy of C(p,q). On the other hand, we construct a (consistent) example of a pseudocompact (countably compact) Tychonoff semigroup containing a copy of C(p,q).     

Vertex Turán problems in the hypercube

Let Qn be the n-dimensional hypercube: the graph with vertex set n{0,1} and edges between vertices that differ in exactly one coordinate. For 1?d?n and F⊆d{0,1} we say that S⊆n{0,1} is F-free if every embedding satisfies i(F)?S. We consider the question of how large S⊆n{0,1} can be if it is F-free. In particular we generalise the main prior result in this area, for F=²{0,1}, due to E.A. Kostochka and prove a local stability result for the structure of near-extremal sets.We also show that the density required to guarantee an embedded copy of at least one of a family of forbidden configurations may be significantly lower than that required to ensure an embedded copy of any individual member of the family.Finally we show that any subset of the n-dimensional hypercube of positive density will contain exponentially many points from some embedded d-dimensional subcube if n is sufficiently large.     

Partitioning complete graphs by heterochromatic trees

A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t _r (G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most t _r (K _n ) vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of K _n .     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007