An extremal theorem in the hypercube

For a given undirected graph $G$, an \emph{ordered} subset $S = {s_1,s_2,...,s_k} \subseteq V$ of vertices is a resolving set for the graph if the vertices of the graph are distinguishable by their vector of distances to the vertices in $S$. While a superset of any resolving set is always a resolving set, a proper subset of a resolving set is not necessarily a resolving set, and we are interested in determining resolving sets that are minimal or that are minimum (of minimal c...

Given a connected graph $G$ and a non-negative integer $g$, the {\em $g$-extra connectivity} $\k_g(G)$ of $G$ is the minimum cardinality of a set of vertices in $G$, if it exists, whose deletion disconnects $G$ and leaves each remaining component with more than $g$ vertices. This paper focuses on the $g$-extra connectivity of hypercube-like networks (HL-networks for short) which includes numerous well-known topologies, such as hypercubes, twisted cubes, crossed cubes and M\"o...

Let a 2 to 1 directed hypergraph be a 3-uniform hypergraph where every edge has two tail vertices and one head vertex. For any such directed hypergraph F let the nth extremal number of F be the maximum number of edges that any directed hypergraph on n vertices can have without containing a copy of F. There are actually two versions of this problem: the standard version where every triple of vertices is allowed to have up to all three possible directed edges and the oriented v...

We construct a set of positive integers A in {1,..., n} with |A|>> n^{2/3} that does not contain Hilbert cubes of dimension 3. As a consequence we prove that ex(n; K^(3)(2,2,2))>> n^{8/3} where K^(3)(2,2,2) is the simplest complete 3-partite hypergraph. This is the first case of an improvement on the trivial lower bound for ex(n; L) when L is a complete r-partite hypergraph.

There are different concepts regarding to tree decomposition of a graph $G$. For the Hypercube $Q_n$, these concepts have been shown to have many applications. But some diverse papers on this subject make it difficult to follow what is precisely known. In this note first we will mention some known results on the tree decomposition of hypercubes and then introduce new explicit constructions for the previously known and unknown cases.

A graph $G$ is said to be {\it $2$-distinguishable} if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the labels. The minimum size of a label class, over all 2-distinguishing labelings, is called the {\it cost of $2$-distinguishing}, denoted by $\rho(G)$. For $n\geq 4$ the hypercubes $Q_n$ are 2-distinguishable, but the values for $\rho(Q_n)$ have been elusive, with only bounds and partial results previously known. This pap...

Given a subgraph G of the hypercube Q_n, a coloring of the edges of Q_n such that every embedding of G contains an edge of every color is called a G-polychromatic coloring. The maximum number of colors with which it is possible to G-polychromatically color the edges of any hypercube is called the polychromatic number of G. To determine polychromatic numbers, it is only necessary to consider a structured class of colorings, which we call simple. The main tool for finding upper...

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that "any graph is close to being the disjoint union of expanders". Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. These results are obtained as corollaries of a new family of graphs, which we construct by pi...

The cube Q is the usual 8-vertex graph with 12 edges. Here we give a new proof for a theorem of Erd\H{o}s and Simonovits concerning the Tur\'an number of the cube. Namely, it is shown that e(G) < n^{8/5}+(2n)^{3/2} holds for any n-vertex cube-free graph G. Our aim is to give a self-contained exposition. We also point out the best known results and supply bipartite versions.

Let $L(G)$ denote the maximum number of leaves in any spanning tree of a connected graph $G$. We show the (known) result that for the $n$-cube $Q_n$, $L(Q_n) \sim 2^n = |V(Q_n)|$ as $n\rightarrow \infty$. Examining this more carefully, consider the minimum size of a connected dominating set of vertices $\gamma_c(Q_n)$, which is $2^n-L(Q_n)$ for $n\ge2$. We show that $\gamma_c(Q_n)\sim 2^n/n$. We use Hamming codes and an "expansion" method to construct leafy spanning trees in ...