Search

We first briefly summarize several well-known properties of regular tessellations of the three two-dimensional maximally symmetric manifolds, E2, S2, and H2, by bounded regular tiles. For instance, there exist infinitely many regular tessellations of the hyperbolic plane H2 by curved hyperbolic equilateral triangles whose vertex angles are 2π/d for d=7,8,9,… On the other hand, we prove that there is no curved hyperbolic regular tetrahedron which tessellates the three-dimensional hyperbolic space H3. We also show that a regular tessellation of H3 can only consist of the hyperbolic cubes, hyperbolic regular icosahedra, or two types of hyperbolic regular dodecahedra. There exist only two regular hyperbolic space-fillers of H4. If n>4, then there exists no regular tessellation of Hn.

Abstract We prove that the (n − 2) -dimensional surface area (perimeter) of central hyperplane sections of the n -dimensional unit cube is maximal for the hyperplane perpendicular to the vector (1 , 1 , 0 , ... , 0). This gives a positive answer to a question of Pełczyński who solved the three dimensional case. We study both the real and the complex versions of this problem. We also use our result to show that the answer to an analogue of the Busemann–Petty problem for the surface area is negative in dimensions 14 and higher. [ABSTRACT FROM AUTHOR]

A Gray code of size n is a cyclic sequence of all binary words of length n such that two consecutive words differ exactly in one position. We say that the Gray code is a distance code if the Hamming distance between words located at distance k from each other is equal to d. The distance property generalizes the familiar concepts of a locally balanced Gray code. We prove that there are no distance Gray codes with d = 1 for k > 1. Some examples of constructing distance Gray codes are given. For one infinite series of parameters, it is proved that there are no distance Gray codes. [ABSTRACT FROM AUTHOR]

In previous works, some of the authors have proposed a canonical form of Gray Codes (GCs) in N-cubes (hypercubes of dimension N). This form allowed them to draw an algorithm that theoretically provides exactly all the GCs for a given dimension N. In another work, we first have shown that any of these GC can be used to build the transition function of a Pseudorandom Number Generator (PRNG). Also, we have found a theoretical quadratic upper bound of the mixing time, i.e., the number of iterations that are required to provide a PRNG whose output is uniform. This article, extends these two previous works both practically and theoretically. On the one hand, another algorithm for generating GCs is proposed that provides an efficient generation of subsets of the entire set of GCs related to a given dimension N. This offers a large choice of GC to be used in the construction of Choatic Iterations based PRNGs (CI-PRNGs), leading to a large class of possible PRNGs. On the other hand, the mixing time has been theoretically shown to be in Nlog(N), which was anticipated in the previous article, but not proven.

We present two main results: a 2-page and a rectilinear drawing of the n-dimensional cube [ABSTRACT FROM AUTHOR]

Walks on the representation graph $${\mathcal{R}_{\mathsf{V}}}$$ ( G) determined by a group G and a G-module V are related to the centralizer algebras of the action of G on the tensor powers $${\mathsf{V}^{\otimes k}}$$ via Schur-Weyl duality. This paper explores that connection when the group is $${\mathbb{Z}^{n}_{2}}$$ and the module V is chosen so the representation graph is the n-cube. We describe a basis for the centralizer algebras in terms of labeled partition diagrams. We obtain an expression for the number of walks by counting certain partitions and determine the exponential generating functions for the number of walks. [ABSTRACT FROM AUTHOR]

For an integer $$n\ge 2$$ , the triangular graph has vertex set the 2-subsets of $$\{1,\ldots ,n\}$$ and edge set the pairs of 2-subsets intersecting at one point. Such graphs are known to be halved graphs of bipartite rectagraphs, which are connected triangle-free graphs in which every 2-path lies in a unique quadrangle. We refine this result and provide a characterisation of connected locally triangular graphs as halved graphs of normal quotients of n-cubes. To do so, we study a parameter that generalises the concept of minimum distance for a binary linear code to arbitrary automorphism groups of the n-cube. [ABSTRACT FROM AUTHOR]

A topological index is a single number descriptor that characterizes the molecular graph topology up to isomorphism. Hyper-tubes, open or closed, consisting of hyper-cubes of n-dimensions have been designed and formulas for some topological indices, counting vary substructures or characteristics, were established. [ABSTRACT FROM AUTHOR]

We consider locally balanced Gray codes.We say that a Gray code is locally balanced if every 'short' subword in its transition sequence contains all letters of the alphabet |1, 2,..., n~. The minimal length of these subwords is the window width of the code. We show that for each n ≥ 3 there exists a Gray code with window width at most n + 3⌊log n⌋. [ABSTRACT FROM AUTHOR]

Local domains of n-spaces surrounded by the common Euclidean 3D-space may exist in complex chemical (mineral or synthetic) structures. In this paper, two classes of the simplest clusters embedded in n-dimensional spaces higher than three are designed by operations on maps and their properties discussed. [ABSTRACT FROM AUTHOR]

Abstract: Let G be a finite abelian group, let E be a subset of G, and form the Cayley (directed) graph of G with connecting set E. We explain how, for various matrices associated to this graph, the spectrum can be used to give information on the Smith normal form. This technique is applied to several interesting examples, including matrices in the Bose–Mesner algebra of the Hamming association scheme . We also recover results of Bai and Jacobson–Niedermaier–Reiner on the critical group of a Cartesian product of complete graphs. [Copyright &y& Elsevier]

We consider the non-commuting graph ∇(G) of a non-abelian finite group G; its vertex set is G\Z(G), the set of non-central elements of G, and two distinct vertices x and y are joined by an edge if [x, y] ≠ 1. We determine the structure of any finite non-abelian group G (up to isomorphism) for which ∇(G) is a complete multipartite graph (see Propositions 3 and 4). It is also shown that a non-commuting graph is a strongly regular graph if and only if it is a complete multipartite graph. Finally, it is proved that there is no non-abelian group whose non-commuting graph is self-complementary and n-cube. [ABSTRACT FROM AUTHOR]

Under study is the relationship between the eigenfunctions of the Johnson and Hamming graphs. An eigenfunction of a graph is an eigenvector of its adjacency matrix with some eigenvalue; moreover, an eigenfunction can be identically zero. We find a criterion for the embeddability of an eigenfunction of the Johnson graph J( n, w) with a given eigenvalue into a certain eigenfunction of the Hamming graph with a given eigenvalue. [ABSTRACT FROM AUTHOR]

The cycle automorphism in the n-cube is an automorphism of the cube which keeps some cycle in its place and does not change its orientation. An upper bound is found for the order of the group of cycle automorphisms in the n-cube. We obtain the construction for building the long simple cycles for which the order of the group reaches the upper bound. [ABSTRACT FROM AUTHOR]

Abstract: We study the volume of slabs in the 2- and 3-dimensional cube as a function of the width and the defining direction. The variational method yields that there exist surprisingly many local extrema and saddle points of the volume of the slabs. We give several general formula for the volume of sections and slabs of the n-cube. [Copyright &y& Elsevier]

We obtain an upper bound for the order of the group of orientation-preserving automorphisms of a Hamiltonian cycle in the Boolean n-cube. We prove that the existence of a Hamiltonian cycle with the order of the group of orientation-preserving automorphisms attaining this upper bound is equivalent to the existence of a Hamiltonian cycle with an additional condition on the graph of orbits of a fixed automorphism of the n-cube. [ABSTRACT FROM AUTHOR]

2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B be the number of balanced 2-colorings of the n-cube with 2 k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence $\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}$ is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B for fixed k, and by probabilistic method we show that it holds when n is sufficiently large. [ABSTRACT FROM AUTHOR]

The notion of partitional graphs, a subclass of sequential graphs, is introduced, and the cartesian product of a partitional graph and K2 is shown to be partitional. Every sequential graph is harmonious and felicitous. The partitional property of some bipartite graphs including the n-dimensional cube Q n is studied, and thus this paper extends what was known about the sequentialness, harmoniousness and felicitousness of such graphs. [ABSTRACT FROM AUTHOR]

The connectivity properties of a mobile linear network with high speed mobile nodes and strict delay constraint are investigated. A new mobility model is developed to represent the steady state node distribution, and it accurately captures the statistical properties of random node arrival, time-varying node speed, and the distinct behaviors of nodes following different traffic patterns. With the mobility model, the statistical properties of network connectivity are studied and identified. Unlike most previous works that do not consider the impacts of transmission latency, which is critical for real time applications, this paper identifies the quantitative relationship between network connectivity and delay constraint. The results are applicable to both delay constrained networks and delay tolerant networks. The connectivity analysis is performed with a novel geometry-assisted analytical method. Exact connectivity probability expressions are developed by using the volumes of a hypercube intersected by a hyperplane, and a hyperpyramid. The geometry-assisted analytical method significantly simplifies the connectivity analysis. [ABSTRACT FROM AUTHOR]

Abstract: Complexity issues intrinsic to certain fundamental data dissemination problems in high-performance network topologies are discussed. In particular, we study the p-pairwise edge disjoint shortest paths problem. An efficient algorithm for the case when every source point is at a distance at most two from its target is presented and for pairs at a distance at most three we show that the problem is NP-complete. [Copyright &y& Elsevier]

The t-pebbling number of graph G, ft(G), is the least positive integer q such that these q pebbles are placed oil the vertices of G. however we can move t pebbles to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. In this paper, we compute the t-pebbling number of complete graph, n-star, cycle, n-cube, path and tree. We also characterise the t-pebbling number of a tree. [ABSTRACT FROM AUTHOR]

Abstract: It is a difficult theoretical and computational problem to describe explicitly the list of hyper-planes spanned by the vertices of the n-cube. In this paper we describe a procedure to generate hyper-planes of the n-cube from hyper-planes of the (n−1)-cube. Our main theorem says that starting with the hyper-planes of the 1-cube and iterating this procedure we obtain the complete list of hyper-planes of the n-cube up till n=6. For n=7, with this procedure, not all the hyper-planes are obtained. An explicit description of the hyper-planes of the 7-cube is given, followed by a brief analysis of some further consequences of the results obtained. [Copyright &y& Elsevier]

H. Bailey and D. DeTemple [1] considered some properties of squares inscribed in triangles. In this article we generalise their results to the n-dimensional space. [ABSTRACT FROM AUTHOR]

In parallel and distributed systems many communications take place concurrently, so the routing algorithm as well as the underlying interconnection network play a vital role in delivering all the messages efficiently. Fault tolerance and performance are often obtained by delivering the messages through node disjoint shortest paths. In this paper we present two efficient algorithms to construct, under certain conditions, pairwise node disjoint shortest paths for pairs of vertices in an n-cube in the presence of faulty nodes. The first algorithm has O(m2) time complexity, where m is the number of input bits, and the second one takes O(m3), but it solves more general problem instances. We also present an efficient algorithm for the extreme version of the edge disjoint shortest paths problem when n is odd. [Copyright &y& Elsevier]

The acyclic point-connectivity of a graph G, denoted α(G), is the minimum number of points whose removal from G results in an acyclic graph. In a 1975 paper, Harary stated erroneously that α(Qn)=2n−1−1 where Qn denotes the n-cube. We prove that for n>4, 7⋅2n−4≤α(Qn)≤2n−1−2n−y−2, where y=[log2(n−1)]. We show that the upper bound is obtained for n≤8 and conjecture that it is obtained for all n.

In previous works, some of the authors have proposed a canonical form of Gray Codes (GCs) in N -cubes (hypercubes of dimension N). This form allowed them to draw an algorithm that theoretically provides exactly all the GCs for a given dimension N. In another work, we first have shown that any of these GC can be used to build the transition function of a Pseudorandom Number Generator (PRNG). Also, we have found a theoretical quadratic upper bound of the mixing time, i.e., the number of iterations that are required to provide a PRNG whose output is uniform. This article, extends these two previous works both practically and theoretically. On the one hand, another algorithm for generating GCs is proposed that provides an efficient generation of subsets of the entire set of GCs related to a given dimension N. This offers a large choice of GC to be used in the construction of Choatic Iterations based PRNGs (CI-PRNGs), leading to a large class of possible PRNGs. On the other hand, the mixing time has been theoretically shown to be in N log (N) , which was anticipated in the previous article, but not proven. [ABSTRACT FROM AUTHOR]