Nilpotent 1‐factorizations of the complete graph

For which groups G of even order 2n does a 1‐factorization of the complete graph K_2n exist with the property of admitting G as a sharply vertex‐transitive automorphism group? The complete answer is still unknown. Using the definition of a starter in G introduced in 4 , we give a positive answer for new classes of groups; for example, the nilpotent groups with either an abelian Sylow 2‐subgroup or a non‐abelian Sylow 2‐subgroup which possesses a cyclic subgroup of index 2. Further considerations are given in case the automorphism group G fixes a 1‐factor. © 2005 Wiley Periodicals, Inc. J Combin Designs     

On B(5, 18) Groups

A group G is said to be a B(n, k) group if for any n-element subset A of G, |A²| ≤k. In this paper, a characterization of B(5, 18) groups is given. It is shown that G is a B(5, 18) group if and only if one of the following statements holds: (1) G is abelian; (2) |G| ≤18; (3) G ? ? a, b | a⁵ = b⁴ = 1, a^b = a^?1 ?.     

Group connectivity of complementary graphs

Let G be a 2‐edge‐connected undirected graph, A be an (additive) abelian group and A* = A?{0}. A graph G is A‐connected if G has an orientation D(G) such that for every function b: V(G)?A satisfying , there is a function f: E(G)?A* such that for each vertex v∈V(G), the total amount of f values on the edges directed out from v minus the total amount of f values on the edges directed into v equals b(v). For a 2‐edge‐connected graph G, define Λ_g(G) = min{k: for any abelian group A with |A|?k, G is A‐connected }. In this article, we prove the following Ramsey type results on group connectivity:

1. Let G be a simple graph on n?6 vertices. If min{δ(G), δ(G^c)}?2, then either Λ_g(G)?4, or Λ_g(G^c)?4.
2. Let Z₃ denote the cyclic group of order 3, and G be a simple graph on n?44 vertices. If min{δ(G), δ(G^c)}?4, then either G is Z₃‐connected, or G^c is Z₃‐connected. © 2011 Wiley Periodicals, Inc. J Graph Theory

     

On the maximum size of a k-zero-free set in an abelian group

A subset A of elements in an abelian group G is called k-zero-free if the equation x ₁ + x ₂ + ... + x _k = 0 has no solution in A. A k-zero-free set A in G is called maximal if A ∪ {x} is k-zero-free for no x ∈ G\A. Some bounds for the maximum size of a k-zero free set are obtained. In particular, we determine the maximum speed of a k-zero-free arithmetic progression in the cyclic group Z _n and find the upper and lower bounds for the maximum size of a k-zero-free set in an abelian group G. We describe the structure of a maximal k-zero-free set A in the cyclic group Z _n provided that gcd(n, k) = 1 and k|A| ≥ n + 1.     

On the extendability of certain semi-Cayley graphs of finite abelian groups

A connected graph Γ with at least 2n+2 vertices is said to be n-extendable if every matching of size n in Γ can be extended to a perfect matching. The aim of this paper is to study the 1-extendability and 2-extendability of certain semi-Cayley graphs of finite abelian groups, and the classification of connected 2-extendable semi-Cayley graphs of finite abelian groups is given. Thus the 1-extendability and 2-extendability of Cayley graphs of non-abelian groups which can be realized as such semi-Cayley graphs of abelian groups can be deduced. In particular, the 1-extendability and 2-extendability of connected Cayley graphs of generalized dicyclic groups and generalized dihedral groups are characterized.     

Uniform Boundedness of Torsion Subgroups of Linear Groups

The torsion conjecture says： for any abelian variety A defined over a number field k, the order of the torsion subgroup of A（k） is bounded by a constant C（k,d） which depends only on the number field k and the dimension d of the abelian variety. The torsion conjecture remains open in general. However, in this paper, a short argument shows that the conjecture is true for more general fields if we consider linear groups instead of abelian varieties. If G is a connected linear algebraic group defined over a field k which is finitely generated over Q,Г is a torsion subgroup of G（k）. Then the order of Г is bounded by a constant C＇（k, d） which depends only on k and the dimension d of G.     

On automorphism groups of Cayley graphs

LetX _G,H denote the Cayley graph of a finite groupG with respect to a subsetH. It is well-known that its automorphism groupA(X_G,H) must contain the regular subgroupL _G corresponding to the set of left multiplications by elements ofG. This paper is concerned with minimizing the index [A(X_G,H)L_G] for givenG, in particular when this index is always greater than 1. IfG is abelian but not one of seven exceptional groups, then a Cayley graph ofG exists for which this index is at most 2. Nearly complete results for the generalized dicyclic groups are also obtained.     

Symmetry groups of vertex-transitive polytopes

Groups which are not isomorphic to the symmetry group of any vertextransitive polytope (of any dimension) are characterized as generalized dicyclic, or abelian groups but not elementary 2-groups. The same class of groupsG is also characterized by the existence of a permutation groupP acting onG, containingG* (the regular representation ofG) as a proper subgroup, such that the members of the stabilizerP _u of the unitu ε G take everyg ε G tog ^±1.     

k-ordered Hamiltonian graphs

A hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordered graphs with small maximum degree is investigated; in particular, a family of 4-regular 4-ordered graphs is described. A graph G of order n ≥ 3 is k-hamiltonian-connected, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices, G contains a v₁-v_k hamiltonian path that encounters v₁, v₂,…, v_k in this order. It is shown that for k ≥ 3, every (k + 1)-hamiltonian-connected graph is k-ordered and a result of Ore on hamiltonian-connected graphs is generalized to k-hamiltonian-connected graphs. © 1997 John Wiley & Sons, Inc.     

The Number of <Emphasis Type="Italic">k</Emphasis>-Sumsets in an Abelian Group

Let G be an abelian group of order n. The sum of subsets A₁,...,A_k of G is defined as the collection of all sums of k elements from A₁,...,A_k; i.e., A₁ + A₂ + · · · + A_k = {a₁ + · · · + a_k | a₁ ∈ A₁,..., a_k ∈ A_k}. A subset representable as the sum of k subsets of G is a k-sumset. We consider the problem of the number of k-sumsets in an abelian group G. It is obvious that each subset A in G is a k-sumset since A is representable as A = A₁ + · · · + A_k, where A₁ = A and A₂ = · · · = A_k = {0}. Thus, the number of k-sumsets is equal to the number of all subsets of G. But, if we introduce a constraint on the size of the summands A₁,...,A_k then the number of k-sumsets becomes substantially smaller. A lower and upper asymptotic bounds of the number of k-sumsets in abelian groups are obtained provided that there exists a summand A_i such that |A_i| = n log^qn and |A₁ +· · ·+ A_i-1 + A_i+1 + · · ·+A_k| = n log^qn, where q = -1/8 and i ∈ {1,..., k}.     

Abelian Group Gradings on Full Matrix Rings

For positive integers ? and n, several authors studied ?_?-gradings of the full matrix ring M _n (k) over a field k. In this article, we show that every (G × H)-grading of M _n (k) can be constructed by a pair of compatible G-grading and H-grading of M _n (k), where G and H are any finite groups. When G and H are finite cyclic groups, we characterize all (G × H)-gradings which are isomorphic to a good grading. Moreover, the results can be generalized for any finite abelian group grading of M _n (k).     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

Steinitz classes of tamely ramified Galois extensions of algebraic number fields

The Steinitz class of a number field extension K/k is an ideal class in the ring of integers Ok of k, which, together with the degree [K:k] of the extension determines the Ok-module structure of OK. We call Rt(k,G) the set of classes which are Steinitz classes of a tamely ramified G-extension of k. We will say that those classes are realizable for the group G; it is conjectured that the set of realizable classes is always a group. We define A^′-groups inductively, starting with abelian groups and then considering semidirect products of A^′-groups with abelian groups of relatively prime order and direct products of two A^′-groups. Our main result is that the conjecture about realizable Steinitz classes for tame extensions is true for A^′-groups of odd order; this covers many cases not previously known. Further we use the same techniques to determine Rt(k,Dn) for any odd integer n. In contrast with many other papers on the subject, we systematically use class field theory (instead of Kummer theory and cyclotomic descent).     

Cycles containing all vertices of maximum degree

For a graph G and an integer k, denote by V_k the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |V_k| ≤ k, then G has a cycle containing all vertices of V_k. It is shown that the upper bound k on |V_k| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |V_k| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc.     

Identities of the soluble product of abelian groups

We consider the product G of abelian groups in the variety \mathfrakAⁿ \mathfrak{A}^n of soluble groups of length at most n. Provided that the abelian factors are decomposable into direct products of cyclic groups, we find necessary and sufficient conditions for G to generate the variety \mathfrakAⁿ \mathfrak{A}^n .     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Pentagons and cycle coverings

Let G be a graph of order n ≥ 5k + 2, where k is a positive integer. Suppose that the minimum degree of G is at least ?(n + k)/2?. We show that G contains k pentagons and a path such that they are vertex‐disjoint and cover all the vertices of G. Moreover, if n ≥ 5k + 7, then G contains k + 1 vertex‐disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.     

Extremal graphs in connectivity augmentation

Let A(n, k, t) denote the smallest integer e for which every k‐connected graph on n vertices can be made (k + t)‐connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge‐connectivity and also for directed vertex‐connectivity. For undirected vertex‐connectivity we determine A(n, k, 1) for all values of n and k. We also describe the graphs that attain the extremal values. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 179–193, 1999     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003