Some Turán type results on the hypercube

For graphs H,G a classical problem in extremal graph theory asks what proportion of the edges of H a subgraph may contain without containing a copy of G. We prove some new results in the case where H is a hypercube. We use a supersaturation technique of Erd?s and Simonivits to give a characterization of a set of graphs such that asymptotically the answer is the same when G is a member of this set and when G is a hypercube of some fixed dimension. We apply these results to a specific set of subgraphs of the hypercube called Fibonacci cubes. Additionally, we use a coloring argument to prove new asymptotic bounds on this problem for a different set of graphs. Finally we prove a new asymptotic bound for the case where G is the cube of dimension 3.     

Netlike partial cubes I. General properties

A set A of vertices of a graph G is C-convex if the vertex set of any cycle of the subgraph of G induced by the union of the intervals between each pair of elements of A is contained in A. A partial cube (isometric subgraph of a hypercube) is a netlike partial cube if, for each edge ab, the sets U_ab and U_ba are C-convex (U_ab being the set of all vertices closer to a than to b and adjacent to some vertices closer to b than to a, and vice versa for U_ba). Particular netlike partial cubes are median graphs, even cycles, benzenoid graphs and cellular bipartite graphs. In this paper we give different characterizations and properties of netlike partial cubes. In particular, as median graphs and cellular bipartite graphs, these graphs have a pre-hull number which is at most one, and moreover the convex hull of any isometric cycle of a netlike partial cube is, as in the case of bipartite cellular graphs, this cycle itself or, as in the case of median graphs, a hypercube. We also characterize the gated subgraphs of a netlike partial cube, and we show that the gated amalgam of two netlike partial cubes is a netlike partial cube.     

Cube-complements of generalized Fibonacci cubes

The generalized Fibonacci cube $Q_h\left(f\right)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. If $G$ is an induced subgraph of $Q_h$, then the cube-complement of $G$ is the graph induced by the vertices of $Q_h$ which are not in $G$. In particular, the cube-complement of a generalized Fibonacci cube $Q_h\left(f\right)$ is the subgraph of $Q_h$ induced by the set of all vertices that contain $f$ as a substring. The questions whether a cube-complement of a generalized Fibonacci cube is (i) connected, (ii) an isometric subgraph of a hypercube or (iii) a median graph are studied. Questions (ii) and (iii) are completely solved, i.e. the sets of binary strings that allow a graph of this class to be an isometric subgraph of a hypercube or a median graph are given. The cube-complement of a daisy cube is also studied.     

Cube Polynomial of Fibonacci and Lucas Cubes

The cube polynomial of a graph is the counting polynomial for the number of induced k-dimensional hypercubes (k≥0). We determine the cube polynomial of Fibonacci cubes and Lucas cubes, as well as the generating functions for the sequences of these cubes. Several explicit formulas for the coefficients of these polynomials are obtained, in particular they can be expressed with convolved Fibonacci numbers. Zeros of the studied cube polynomials are explicitly determined. Consequently, the coefficients sequences of cube polynomials of Fibonacci and Lucas cubes are unimodal.     

All good (bad) words consisting of 5 blocks

Generalized Fibonacci cube Q_d(f), introduced by Ilic, Klavzar and Rho, is the graph obtained from the hypercube Q_d by removing all vertices that contain f as factor. A word f is good if Q_d(f) is an isometric subgraph of Q_d for all d ≥ 1, and bad otherwise. A non-extendable sequence of contiguous equal digits in a word μ is called a block of μ. Ilic, Klavzar and Rho shown that all the words consisting of one block are good, and all the words consisting of three blocks are bad. So a natural problem is to study the words consisting of other odd number of blocks. In the present paper,a necessary condition for a word consisting of odd number of blocks being good is given, and all the good(bad) words consisting of 5 blocks is determined.     

The degree sequence of Fibonacci and Lucas cubes

The Fibonacci cube Γ_n is the subgraph of the n-cube induced by the binary strings that contain no two consecutive 1’s. The Lucas cube Λ_n is obtained from Γ_n by removing vertices that start and end with 1. It is proved that the number of vertices of degree k in Γ_n and Λ_n is and , respectively. Both results are obtained in two ways, since each of the approaches yields additional results on the degree sequences of these cubes. In particular, the number of vertices of high resp. low degree in Γ_n is expressed as a sum of few terms, and the generating functions are given from which the moments of the degree sequences of Γ_n and Λ_n are easily computed.     

Asymptotic Properties of Fibonacci Cubes and Lucas Cubes

It is proved that the asymptotic average eccentricity and the asymptotic average degree of both Fibonacci cubes and Lucas cubes are \({(5+\sqrt{5})/10}\) and \({(5-\sqrt{5}) /5}\) , respectively. A new labeling of the leaves of Fibonacci trees is introduced and it is proved that the eccentricity of a vertex of a given Fibonacci cube is equal to the depth of the associated leaf in the corresponding Fibonacci tree. Hypercube density is also introduced and studied. The hypercube density of both Fibonacci cubes and Lucas cubes is shown to be \({(1-1/\sqrt{5})/ \rm log_ {2}\varphi}\) , where \({\varphi}\) is the golden ratio, and the Cartesian product of graphs is used to construct families of graphs with a fixed, non-zero hypercube density. It is also proved that the average ratio of the numbers of Fibonacci strings with a 0 (a 1, respectively) in a given position, where the average is taken over all positions, converges to \({\varphi^{2}}\) , and likewise for Lucas strings.     

Maximum Matchings in the n-Dimensional Cube

The problem of efficient computation of maximum matchings in the n-dimensional cube, which is applied in coding theory, is solved. For an odd n, such a matching can be found by the method given in our Theorem 2. This method is based on the explicit construction (Theorem 1) of the maps of the vertex set that induce largest matchings in any bipartite subgraph of the n-dimensional cube for any n.     

The distinguishing number of the augmented cube and hypercube powers

The distinguishing number of a graph G, denoted D(G), is the minimum number of colors such that there exists a coloring of the vertices of G where no nontrivial graph automorphism is color-preserving. In this paper, we answer an open question posed in Bogstad and Cowen [The distinguishing number of the hypercube, Discrete Math. 283 (2004) 29-35] by showing that the distinguishing number of , the pth graph power of the n-dimensional hypercube, is 2 whenever 2<p<n-1. This completes the study of the distinguishing number of hypercube powers. We also compute the distinguishing number of the augmented cube AQ_n, a variant of the hypercube introduced in Choudum and Sunitha [Augmented cubes, Networks 40 (2002) 71-84]. We show that D(AQ₁)=2; D(AQ₂)=4; D(AQ₃)=3; and D(AQ_n)=2 for n?4. The sequence of distinguishing numbers answers a question raised in Albertson and Collins [An introduction to symmetry breaking in graphs, Graph Theory Notes N.Y. 30 (1996) 6-7].     

Bivariate fibonacci like p-polynomials

In this article, we study the bivariate Fibonacci and Lucas p-polynomials (p ? 0 is integer) from which, specifying x, y and p, bivariate Fibonacci and Lucas polynomials, bivariate Pell and Pell-Lucas polynomials, Jacobsthal and Jacobsthal-Lucas polynomials, Fibonacci and Lucas p-polynomials, Fibonacci and Lucas p-numbers, Pell and Pell-Lucas p-numbers and Chebyshev polynomials of the first and second kind, are obtained. Afterwards, we obtain some properties of the bivariate Fibonacci and Lucas p-polynomials.     

Pell graphs

In this paper, we introduce the Pell graphs, a new family of graphs similar to the Fibonacci cubes. They are defined on certain ternary strings (Pell strings) and turn out to be subgraphs of Fibonacci cubes of odd index. Moreover, as well as ordinary hypercubes and Fibonacci cubes, Pell graphs have several interesting structural and enumerative properties. Here, we determine some of them. Specifically, we obtain a canonical decomposition giving a recursive structure, some basic properties (bipartiteness and existence of maximal matchings), some metric properties (radius, diameter, center, periphery, medianicity), some properties on subhypercubes (cube coefficients and polynomials, cube indices, decomposition in subhypercubes), and, finally, the distribution of the degrees.     

Clique matchings in the <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-dimensional cube

A clique matching in the k-ary n-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the k-ary n-dimensional cube can be expressed as the k-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the k-ary n-dimensional cube for an arbitrary positive integer k as n→∞.     

Vertex and Edge Orbits of Fibonacci and Lucas Cubes

The Fibonacci cube \({\Gamma_{n}}\) is obtained from the n-cube Q _n by removing all the vertices that contain two consecutive 1s. If, in addition, the vertices that start and end with 1 are removed, the Lucas cube \({\Lambda_{n}}\) is obtained. The number of vertex and edge orbits, the sets of the sizes of the orbits, and the number of orbits of each size, are determined for the Fibonacci cubes and the Lucas cubes under the action of the automorphism group. In particular, the set of vertex orbit sizes of \({\Lambda_{n}}\) is \({\{k \geq 1; k |n\} \cup \{k \geq 18; k |2n\}}\), the number of vertex orbits of \({\Lambda_{n}}\) of size k, where k is odd and divides n, is equal to \({\sum_{d | k} \mu (\frac{k}{d})F_{\lfloor{\frac{d}{2}}\rfloor+2}}\), and the number of edge orbits of \({\Lambda_{n}}\) is equal to the number of vertex orbits of \({\Gamma_{n-3}}\). Dihedral transformations of strings and primitive strings are essential tools to prove these results.     

On cubical graphs

It is frequently of interest to represent a given graph G as a subgraph of a graph H which has some special structure. A particularly useful class of graphs in which to embed G is the class of n-dimensional cubes. This has found applications, for example, in coding theory, data transmission, and linguistics. In this note, we study the structure of those graphs G, called cubical graphs (not to be confused with cubic graphs, those graphs for which all vertices have degree 3), which can be embedded into an n-dimensional cube. A basic technique used is the investigation of graphs which are critically nonembeddable, i.e., which can not be embedded but all of whose subgraphs can be embedded.     

Netlike partial cubes II. Retracts and netlike subgraphs

First we show that the class of netlike partial cubes is closed under retracts. Then we prove, for a subgraph G of a netlike partial cube H, the equivalence of the assertions: G is a netlike subgraph of H; G is a hom-retract of H; G is a retract of H. Finally we show that a non-trivial netlike partial cube G, which is a retract of some bipartite graph H, is also a hom-retract of H if and only if G contains at most one convex cycle of length greater than 4.     

Multidimensional Latin bitrades

A subset of the n-dimensional k-valued hypercube is a unitrade or united bitrade whenever the size of its intersections with the one-dimensional faces of the hypercube takes only the values 0 and 2. A unitrade is bipartite or Hamiltonian whenever the corresponding subgraph of the hypercube is bipartite or Hamiltonian. The pair of parts of a bipartite unitrade is an n-dimensional Latin bitrade. For the n-dimensional ternary hypercube we determine the number of distinct unitrades and obtain an exponential lower bound on the number of inequivalent Latin bitrades. We list all possible n-dimensional Latin bitrades of size less than 2 ⁿ⁺¹. A subset of the n-dimensional k-valued hypercube is a t-fold MDS code whenever the size of its intersection with each one-dimensional face of the hypercube is exactly t. The symmetric difference of two single MDS codes is a bipartite unitrade. Each component of the corresponding Latin bitrade is a switching component of one of these MDS codes. We study the sizes of the components of MDS codes and the possibility of obtaining Latin bitrades of a size given from MDS codes. Furthermore, each MDS code is shown to embed in a Hamiltonian 2-fold MDS code.     

Classification of subsets of B n and additive channels

The paper deals with the classification problem for subsets of vertices of a unit n-dimensional cube on the basis of “symmetry.” Applications to the study of additive channels are presented.     

Completely unimodal numberings of a simple polytope

A completely unimodal numbering of the m vertices of a simple d-dimensional polytope is a numbering 0, 1, …,m−1 of the vertices such that on every k-dimensional face (2≤k≤d) there is exactly one local minimum (a vertex with no lower-numbered neighbors on that face). Such numberings are abstract objective functions in the sense of Adler and Saigal [1]. It is shown that a completely unimodal numbering of the vertices of a simple polytope induces a shelling of the facets of the dual simplicial polytope. The h-vector of the dual simplicial polytope is interpreted in terms of the numbering (with respect to using a local-improvement algorithm to locate the vertex numbered 0). In the case that the polytope is combinatorially equivalent to a d-dimensional cube, a ‘successor-tuple’ for each vertex is defined which carries the crucial information of the numbering for local-improvement algorithms. Combinatorial properties of these d-tuples are studied. Finally the running time of one particular local-improvement algorithm, the Random Algorithm, is studied for completely unimodal numberings of the d-cube. It is shown that for a certain class of numberings (which includes the example of Klee and Minty [8] showing that the simplex algorithm is not polynomial and all Hamiltonian saddle-free injective pseudo-Boolean functions [6]) this algorithm has expected running time that is at worst quadratic in the dimension d.     

Hamiltonian paths with prescribed edges in hypercubes

Given a set P of at most 2n-4 prescribed edges (n?5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Q_n contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n?3 there exist vertices u,v and 2n-3 edges of Q_n not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary.     

An optimal pram algorithm for a spanning tree on trapezoid graphs

LetG be a graph withn vertices andm edges. The problem of constructing a spanning tree is to find a connected subgraph ofG withn vertices andn?1 edges. In this paper, we propose anO(logn) time parallel algorithm withO(n/logn), processors on an EREW PRAM for constructing a spanning tree on trapezoid graphs.