On orientation-preserving automorphisms of Hamiltonian cycles in the <Emphasis Type="Italic">N</Emphasis>-dimensional Boolean cube

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.     

Automorphism group and diameter of a graph

Given a connected graph Γ of order n and diameter d, we establish a tight upper bound for the order of the automorphism group of Γ as a function of n and d, and determine the graphs for which the bound is attained. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

An upper bound for Hilbert cubes

In this note we give a new upper bound for the largest size of subset of {1,2,…,n} not containing a k-cube.     

Bounding the size of square-free subgraphs of the hypercube

We investigate the maximum size of a subset of the edges of the n-cube that does not contain a square, or 4-cycle. The size of such a subset is trivially at most 3/4 of the total number of edges, but the proportion was conjectured by Erd?s to be asymptotically 1/2. Following a computer investigation of the 4-cube and the 5-cube, we improve the known upper bound from 0.62284… to 0.62256… in the limit.     

Counting Overlattices in Automorphism Groups of Trees

We give an upper bound for the number u _Γ(n) of “overlattices” in the automorphism group of a tree, containing a fixed lattice Γ with index n. For an example of Γ in the automorphism group of a 2p-regular tree whose quotient is a loop, we obtain a lower bound of the asymptotic behavior as well.     

Automorphisms of imbedded graphs

If a linear graph is imbedded in a surface to form a map, then the map has a group of automorphisms which is a subgroup (usually, a proper subgroup) of the automorphism group of the graph. In this note it will be shown that, for any imbedding of K_n in an orientable surface, the order of the automorphism group of the resulting map is a divisor of n(n − 1), and that the order equals n(n − 1) if and only if n is a prime power. The explicit construction of imbeddings of K_Q, q = p^m with map automorphism group of order q(q − 1) gives rise to new types of regular map. There are also tenous connections with the theory of Frobenius groups.     

The basis number of a graph

MacLane proved that a graph is planar if and only if it has a 2-fold basis for its cycle space. We define the basis number of a graph G to be the least integer k such that G has a k-fold basis for its cycle space. We investigate the basis number of the complete graphs, complete bipartite graphs, and the n-cube.     

Bounds on the number of Hamiltonian circuits in the n-cube

New upper and lower bounds are found for the number of Hamiltonian circuits in the graph of the n-cube.     

Automorphism groups of second order differential equations

The automorphism group of a system ofn second order differential equations is shown to be a Lie group of dimension at mostn ²+n in the autonomous case, and of dimension at most (n+1)² in the heteronomous case. The equations whose automorphism groups have this maximum dimension are classified.     

Enumerating Perfect Matchings in n-Cubes

The perfect matchings in the n-cube have earlier been enumerated for n?≤?6. A dynamic programming approach is here used to obtain the total number of perfect matchings in the 7-cube, which is 391 689 748 492 473 664 721 077 609 089. The number of equivalence classes of perfect matchings is further shown to be 336 in the 5-cube, 356 788 059 in the 6-cube and 607 158 046 495 120 886 820 621 in the 7-cube. The techniques used can be generalized to arbitrary bipartite and general graphs.     

Another universality property for crumpled cubes

Let C denote a crumpled n-cube in the n-sphere Sⁿ such that every Cantor set in its boundary is tamely embedded in Sⁿ. The main theorem shows C to be universal in the sense that however it is sewn to a crumpled n-cube D of type 2A, a large class containing most of the explicitly described examples, the resultant space is homeomorphic to Sⁿ.     

A note on minimal triangulations of an n-cube

This paper is concerned with finding a lower bound for ?(n), the minimum number of simplices required to triangulate an n-cube. We prove that ?(n)≥L_n, where L_n is the minimum value of the sum of n?1 unknowns subject to n?1 inequality constraints. In particular, it is shown that ?(5)≥60.     

Vertex Partitions of Hypercubes into Symmetric Snakes

In his paper (Combinatorica 14 (4) (1994), 491-496) Wojciechowski constructed a snake S, i.e. an induces cycle, in the n-dimensional hypercube Q_n such that for some subgroup G of the automorphism group of Q_n, of order at most 16, the G-translates of S partition the vertex set of Q_n. In this note, we use this snake to obtain a similar result for a symmetric snake with order of G at most 32.     

Splitting automorphisms of order p k of free Burnside groups are inner

It is proved that, if the order of a splitting automorphism of odd period n ≥ 1003 of a free Burnside group B(m, n) is equal to a power of some prime, then the automorphism is inner. Thus, an affirmative answer is given to the question concerning the coincidence of the splitting automorphisms of the group B(m, n) with the inner automorphisms for all automorphisms of order p ^k (p is a prime). This question was posed in 1990 in “Kourovka Notebook” (see the 11th edition, Question 11.36.b).     

Topological invariants of 2-designs arising from difference families

Hefftner, White, Alpert, and others observed a connection between topology and certain block designs with parameters k = 3 and λ = 2. In this paper the connection is extended to include all values of λ. The topology is also exploited further to produce some new invariants of designs. The topology also gives an upper bound for the order of the automorphism group of the designs studied which leads to a generalization of the Bays-Lambossy theorem. Methods for constructing block designs are also given showing that the results apply and are useful for a large class of designs.     

The basis number of the n-cube

The basis number of a graph G is defined as the least integer k such that G has a k-fold basis for its cycle space. MacLane (Fund. Math.28 (1937), 22–32) has shown that a graph is planar if and only if its basis number is ≤2. The basis numbers of certain classes of nonplanar graphs have been previously investigated. The basis number of the n-cube for every n is determined in the paper.     

Some isomorphism results for Thompson-like groups <Emphasis Type="Italic">V</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>(<Emphasis Type="Italic">G</Emphasis>)

The natural automorphism group of a translation surface is its group of translations. For finite translation surfaces of genus g ≥ 2 the order of this group is naturally bounded in terms of g due to a Riemann–Hurwitz formula argument. In analogy with classical Hurwitz surfaces, we call surfaces which achieve the maximal bound Hurwitz translation surfaces. We study for which g there exist Hurwitz translation surfaces of genus g.     

The first order definability of graphs: Upper bounds for quantifier depth

Let D(G) denote the minimum quantifier depth of a first order sentence that defines a graph G up to isomorphism in terms of the adjacency and equality relations. Call two vertices of G similar if they have the same adjacency to any other vertex and denote the maximum number of pairwise similar vertices in G by σ(G). We prove that σ(G)+1?D(G)?max{σ(G)+2,(n+5)/2}, where n denotes the number of vertices of G. In particular, D(G)?(n+5)/2 for every G with no transposition in the automorphism group. If G is connected and has maximum degree d, we prove that for a constant . A linear lower bound for graphs of maximum degree 3 with no transposition in the automorphism group follows from an earlier result by Cai, Fürer, and Immerman [An optimal lower bound on the number of variables for graph identification, Combinatorica 12(4) (1992) 389-410]. Our upper bounds for D(G) hold true even if we allow only definitions with at most one alternation in any sequence of nested quantifiers.In passing we establish an upper bound for a related number D(G,G^′), the minimum quantifier depth of a first order sentence which is true on exactly one of graphs G and G^′. If G and G^′ are non-isomorphic and both have n vertices, then D(G,G^′)?(n+3)/2. This bound is tight up to an additive constant of 1. If we additionally require that a sentence distinguishing G and G^′ is existential, we prove only a slightly weaker bound D(G,G^′)?(n+5)/2.     

Locally triangular graphs and normal quotients of the <Emphasis Type="Italic">n</Emphasis>-cube

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.     

The least number of edges for graphs having dihedral automorphism group

The least (and greatest) number of edges realizable by a graph having n vertices and automorphism group isomorphic to D_2m, the dihedral group of order 2m, is determined for all admissible n.