Simple cycles in the n-cube with a large group of automorphisms

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.     

On automorphisms of infinite graphs with forbidden subgraphs

LexX be anm-connected infinite graph without subgraphs homeomorphic toKm, n, for somen, and let α be an automorphism ofX with at least one cycle of infinite length. We characterize the structure of α and use this characterization to extend a known result about orientation-preserving automorphisms of finite plane graphs to infinite plane graphs. In the last section we investigate the action of α on the ends ofX and show that α fixes at most two ends (Theorem 3.2).     

On cycle—Complete graph ramsey numbers

A new upper bound is given for the cycle-complete graph Ramsey number r(C_m, K_n), the smallest order for a graph which forces it to contain either a cycle of order m or a set of n independent vertices. Then, another cycle-complete graph Ramsey number is studied, namely r(?C_m, K_n) the smallest order for a graph which forces it to contain either a cycle of order / for some / satisfying 3?/?m or a set of n independent vertices. We obtain the exact value of r(?C_m K_n) for all m > n and an upper bound which applies when m is large in comparison with log n.     

On gonality of Riemann surfaces

A compact Riemann surface X is called a (p, n)-gonal surface if there exists a group of automorphisms C of X (called a (p, n)-gonal group) of prime order p such that the orbit space X/C has genus n. We derive some basic properties of (p, n)-gonal surfaces considered as generalizations of hyperelliptic surfaces and also examine certain properties which do not generalize. In particular, we find a condition which guarantees all (p, n)-gonal groups are conjugate in the full automorphism group of a (p, n)-gonal surface, and we find an upper bound for the size of the corresponding conjugacy class. Furthermore we give an upper bound for the number of conjugacy classes of (p, n)-gonal groups of a (p, n)-gonal surface in the general case. We finish by analyzing certain properties of quasiplatonic (p, n)-gonal surfaces. An open problem and two conjectures are formulated in the paper.     

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.     

The Order of Automorphisms of Quasigroups

We prove quadratic upper bounds on the order of any autotopism of a quasigroup or Latin square, and hence also on the order of any automorphism of a Steiner triple system or 1‐factorization of a complete graph. A corollary is that a permutation σ chosen uniformly at random from the symmetric group will almost surely not be an automorphism of a Steiner triple system of order n, a quasigroup of order n or a 1‐factorization of the complete graph . Nor will σ be one component of an autotopism for any Latin square of order n. For groups of order n it is known that automorphisms must have order less than n, but we show that quasigroups of order n can have automorphisms of order greater than n. The smallest such quasigroup has order 7034. We also show that quasigroups of prime order can possess autotopisms that consist of three permutations with different cycle structures. Our results answer three questions originally posed by D.  Stones.     

On κ—ordered Graphs Involved Degree Sum

A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G）≥3κ-1/2 or δ（G）≥5κ-4.Several known results are generalized.     

Construction of hamiltonian cycles with a given spectrum of edge directions in an <Emphasis Type="Italic">n</Emphasis>-dimensional Boolean cube

The spectrum of a Hamiltonian cycle (of a Gray code) in an n-dimensional Boolean cube is the series a = (a ₁, ..., a _n ), where a _i is the number of edges of the ith direction in the cycle. The necessary conditions for the existence of a Gray code with the spectrum a are available: the numbers a _i are even and, for k = 1, ..., n, the sum of k arbitrary components of a is at least 2 ^k . We prove that there is some dimension N such that if the necessary condition on the spectrum is also sufficient for the existence of a Hamiltonian cycle with the spectrum in an N-dimensional Boolean cube then the conditions are sufficient for all dimensions n.     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian

We consider the spectral and algorithmic aspects of the problem of finding a Hamiltonian cycle in a graph. We show that a sufficient condition for a graph being Hamiltonian is that the nontrivial eigenvalues of the combinatorial Laplacian are sufficiently close to the average degree of the graph. An algorithm is given for the problem of finding a Hamiltonian cycle in graphs with bounded spectral gaps which has complexity of order n ^{cln n} .     

Characterization of the unit ball in C<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> among complex manifolds of dimension<Emphasis Type="BoldItalic">n</Emphasis>

We show that if the group of holomorphic automorphisms of a connected complex manifold M of dimension n is isomorphic as a topological group equipped with the compact-open topology to the automorphism group of the unit ball B ⁿ ⊂ ℂ ⁿ ,then M is biholomorphically equivalent to B ⁿ.     

Divisibility in certain automorphism groups

We study solvability of equations of the form x ⁿ = g in the groups of order automorphisms of archimedean-complete totally ordered groups of rank 2. We determine exactly which automorphisms of the unique abelian such group have square roots, and we describe all automorphisms of the general ones.     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

Periodic Endomorphisms of Polycyclic Groups

Let G be a polycyclic group. As a consequence of known results, any periodic group of automorphisms of G is finite and there is an upper bound (depending only on G) for its order. On the other hand, a periodic semigroup of endomorphisms of G need not be finite but we prove that it is locally finite. Also we show that the order of periodic endomorphisms of G is bounded.     

Cycle Lengths in Hamiltonian Graphs with a Pair of Vertices Having Large Degree Sum

A graph of order n is said to be pancyclic if it contains cycles of all lengths from three to n. Let G be a Hamiltonian graph and let x and y be vertices of G that are consecutive on some Hamiltonian cycle in G. Hakimi and Schmeichel showed (J Combin Theory Ser B 45:99–107, 1988) that if d(x) + d(y) ≥ n then either G is pancyclic, G has cycles of all lengths except n − 1 or G is isomorphic to a complete bipartite graph. In this paper, we study the existence of cycles of various lengths in a Hamiltonian graph G given the existence of a pair of vertices that have a high degree sum but are not adjacent on any Hamiltonian cycle in G.     

Powers of Hamiltonian cycles in randomly augmented graphs

We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every k ≥ 1 and sufficiently large n already the minimum degree for an n‐vertex graph G alone suffices to ensure the existence of a kth power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just O(n) random edges ensures the presence of the (k + 1)st power of a Hamiltonian cycle with probability close to one.     

Elliptic K3 Surfaces with Abelian and Dihedral Groups of Symplectic Automorphisms

We analyze K3 surfaces admitting an elliptic fibration ? and a finite group G of symplectic automorphisms preserving this elliptic fibration. We construct the quotient elliptic fibration ?/G comparing its properties to the ones of ?.

We show that if ? admits an n-torsion section, its quotient by the group of automorphisms induced by this section admits again an n-torsion section, and we describe the coarse moduli space of K3 surfaces with a given finite group contained in the Mordell–Weil group.

Considering automorphisms coming from the base of the fibration, we find the Mordell–Weil lattice of a fibration described by Kloosterman, and we find K3 surfaces with dihedral groups as group of symplectic automorphisms. We prove the isometries between lattices described by the author and Sarti and lattices described by Shioda and by Greiss and Lam.     

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.     

Classification of regular embeddings of <Emphasis Type="Italic">n</Emphasis>-dimensional cubes

An orientably-regular map is a 2-cell embedding of a connected graph or multigraph into an orientable surface, such that the group of all orientation-preserving automorphisms of the embedding has a single orbit on the set of all arcs (incident vertex-edge pairs). Such embeddings of the n-dimensional cubes Q _n were classified for all odd n by Du, Kwak and Nedela in 2005, and in 2007, Jing Xu proved that for n=2m where m is odd, they are precisely the embeddings constructed by Kwon in 2004. Here, we give a classification of orientably-regular embeddings of Q _n for all n. In particular, we show that for all even n (=2m), these embeddings are in one-to-one correspondence with elements σ of order 1 or 2 in the symmetric group S _n such that σ fixes n, preserves the set of all pairs B _i ={i,i+m} for 1≤i≤m, and induces the same permutation on this set as the permutation B _i ↦ B _f(i) for some additive bijection f:ℤ _m →ℤ _m . We also give formulae for the numbers of embeddings that are reflexible and chiral, respectively, showing that the ratio of reflexible to chiral embeddings tends to zero for large even n.     

Hyperbolic <Emphasis Type="Italic">n</Emphasis>-dimensional manifolds with automorphism group of dimension <Emphasis Type="Italic">n</Emphasis><Superscript>2</Superscript>

We obtain a complete classification of complex Kobayashihyperbolic manifolds of dimension n ≥ 2, for which the dimension of the group of holomorphic automorphisms is equal to n². Received: May 2005 Accepted: November 2005