A lower bound on solutions of Chartrand's problem

In this paper it is shown that if a connected graphG without loops contains spanning trees withm andn end-vertices, respectively, withm, thenG contains at least spanning trees withk end-vertices for every integerk withm where is the circuit rank ofG.     

Automorphisms of finite groups of bounded rank

LetG be a finite group admitting an automorphismα withm fixed points. Suppose every subgroup ofG isr-generated. It is shown that (1)G has a characteristic soluble subgroupH whose index is bounded in terms ofm andr, and (2) if the orders ofα andG are coprime, then the derived length ofH is also bounded in terms ofm andr. To Professor John Thompson, in honor of his outstanding achievements     

On a class of groups of prime-power order

LetG be a finitep-group,d(G)=dimH ¹ (G, Z _p) andr(G)=dimH ²(G, Z_p). Thend(G) is the minimal number of generators ofG, and we say thatG is a member of a classG _p of finitep-groups ifG has a presentation withd(G) generators andr(G) relations. We show that ifG is any finitep-group, thenG is the direct factor of a member ofG _p by a member ofG _p .     

Conjecture of Li and Praeger concerning the isomorphisms of Cayley graphs of A5

LetG be a finite group, andS a subset ofG \ |1| withS =S ⁻¹. We useX = Cay(G,S) to denote the Cayley graph ofG with respect toS. We callS a Cl-subset ofG, if for any isomorphism Cay(G,S) ≈ Cay(G,T) there is an α∈ Aut(G) such thatS ^α =T. Assume that m is a positive integer.G is called anm-Cl-group if every subsetS ofG withS =S ⁻¹ and | S | ≤m is Cl. In this paper we prove that the alternating groupA ₅ is a 4-Cl-group, which was a conjecture posed by Li and Praeger.     

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.     

(g,f)-Factorizations of graphs orthogonal to [1,2]-subgraph

LetG be a simple graph. Letg(x) andf(x) be integer-valued functions defined onV(G) withf(x)g(x)1 for allxV(G). It is proved that ifG is an (mg+m–1,mf–m+1)-graph andH is a [1,2]-subgraph withm edges, then there exists a (g,f)-factorization ofG orthogonal toH.This work is supported by China Postdoctoral Science Foundation and Shandong Youth Science Foundation.     

(g, f)-factorizations orthogonal to a subgraph in graphs

LetG be a graph with vertex setV (G) and edge setE (G), and letg andf be two integer-valued functions defined on V(G) such thatg(x)⩽(x) for every vertexx ofV(G). It was conjectured that ifG is an (mg +m - 1,mf -m+1)-graph andH a subgraph ofG withm edges, thenG has a (g,f)-factorization orthogonal toH. This conjecture is proved affirmatively. Project supported by the National Natural Science Foundation of China.     

Semiprime Goldie centralizers

LetG be a finite group of automorphisms acting on a ringR, andR ^G={fixed points ofG}. We show that under certain conditions onR andG, whenR ^Gis semiprime Goldie then so isR. In particular, ifa∈R is invertible anda ⁿ∈Z(R), thenR ^G,withG generated by the inner automorphism determined bya, is the centralizer ofa—C _R(a). The above result withR ^Greplaced byC _R(a) is shown without the assumption thata is invertible.     

Two vertex-disjoint cycles in a graph

LetG be a graph of ordern 6 with minimum degree at least (n + 1)/2. Then, for any two integerss andt withs 3,t 3 ands + t n, G contains two vertex-disjoint cycles of lengthss andt, respectively, unless thatn, s andt are odd andG is isomorphic toK _{(n–1)/2,(n–1)/2} + K₁. We also show that ifG is a graph of ordern 8 withn even and minimum degree at leastn/2, thenG contains two vertex-disjoint cycles with any given even lengths provided that the sum of the two lengths is at mostn.     

On long cycles in a 2-connected bipartite graph

Letk be an integer withk 2. LetG = (A, B; E) be a 2-connected bipartite graph. Supposed(x) + d(y) k + 1 for every pair of non-adjacent verticesx andy. ThenG contains a cycle of length at leastmin(2a, 2k) wherea = min(|A|,|B|), unlessG is one of some known exceptions. We conjecture that if|A| = |B| andd(x) + d(y) k + 1 for every pair of non-adjacent verticesx andy withx A andy B, thenG contains a cycle of length at leastmin(2a, 2k).     

Compactness properties of locally compact groups

Compactness propertiesC _n andC P _n for locally compact groupsG are introduced generalizing the finiteness propertiesF _n andF P _n for discrete groups. The propertyC ₁ resp.C ₂ is equivalent withG having a compact set of generators, resp. having a compact presentation. Some basic properties of the compactness propertiesC _n are shown. A local-global principle is proved by the second named author in the adjacent paper of this volume.     

The chromatic polynomial between graph & its complement—about Akiyama and Hararys' open problem

In 1980, Akiyama and Harary proposed the following problem in the Proceedings-Fourth International Graph Theory Conference: “Are there any graphsG which are not self-complementary withG and $\bar G$ having the same chromatic polynomial?”. The problem has been unsolved until now. This paper proves that there are no graphsG which are not self-complementary withG and $\bar G$ having the same chromatic polynomial when |V(G)| =p < 8 orp = 2, 3 (mod 4), there must be a graphG which are not self-complementary withG and $\bar G$ having the same chromatic polynomial when |V(G)| =p ≥ 8 andp ≡ 0, 1 (mod 4).     

Classification of finite groups according to the number of conjugacy classes II

In the following,G denotes a finite group,r(G) the number of conjugacy classes ofG, β(G) the number of minimal normal subgroups ofG andα(G) the number of conjugate classes ofG not contained in the socleS(G). Let Φ _j = {G|β(G) =r(G) −j}. In this paper, the family Φ₁₁ is classified. In addition, from a simple inspection of the groups withr(G) =b conjugate classes that appear in ϒ _j ^=1/11 Φ _j , we obtain all finite groups satisfying one of the following conditions: (1)r(G) = 12; (2)r(G) = 13 andβ(G) > 1; …; (9)r(G) = 20 andβ(G) > 8; (10)r(G) =n andβ(G) =n −a with 1 ≦a ≦ 11, for each integern ≧ 21. Also, we obtain all finite groupsG with 13 ≦r(G) ≦ 20,β(G) ≦r(G) − 12, and satisfying one of the following conditions: (i) 0 ≦α(G) ≦ 4; (ii) 5 ≦α(G) ≦ 10 andS(G) solvable.     

Fan-type theorem for path-connectivity

A graphG is said to bek-path-connected if every pair of distinct vertices inG are joined by a path of length at leastk. We prove that if max{deg _G ^x , deg _G ^y }k for every pair of verticesx,y withd _G (x,y)=2 in a 2-connected graphG, whered _G (x,y) is the distance betweenx andy inG, thenG isk-path-connected.     

Some remarks on subgroups determined by certain ideals in integral group rings

LetG be a group,ZG the integral group ring ofG andI(G) its augmentation ideal. Subgroups determined by certain ideals ofZG contained inI(G) are identified. For example, whenG=HK, whereH, K are normal subgroups ofG andH∩K⊆ζ(H), then the subgroups ofG determined byI(G)I(H)I(G), andI ³(G)I(H) are obtained. The subgroups of any groupG with normal subgroupH determined by (i)I ²(G)I(H)+I(G)I(H)I(G)+I(H)I²(G), whenH′⊆[H,G,G] and (ii)I(G)I(H)I(G) when degH ²(G/H′, T)≤1, are computed. the subgroup ofG determined byI ⁿ(G)+I(G)I(H) whenH is a normal subgroup ofG withG/H free Abelian is also obtained     

An upper bound for conforming Delaunay triangulations

A plane geometric graphC in ℝ² conforms to another such graphG if each edge ofG is the union of some edges ofC. It is proved that, for everyG withn vertices andm edges, there is a completion of a Delaunay triangulation ofO(m ² n) points that conforms toG. The algorithm that constructs the points is also described. Research of the first author is supported by the National Science Foundation under Grant CCR-8921421 and under the Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation. Work of the second author was conducted while he was on study leave at the University of Illinois.     

Cardinal invariants of infinite groups

LetG be a group. CallG akC-group if every element ofG has less thank conjugates. Denote byP(G) the least cardinalk such that any subset ofG of sizek contains two elements which commute.It is shown that the existence of groupsG such thatP(G) is a singular cardinal is consistent withZFC. So is the existence of groupsG which are notkC but haveP(G) wherek is a limit cardinal. On the other hand, ifk is a singular strong limit cardinal, andG is akC-group, thenP(G)k. This partially answers questions, and improves results, of Faber, Laver and McKenzie.The present paper has non-trivial intersection with the author's Diplomarbeit written under the direction of Prof. Ulrich Felgner at the University of Tübingen, W. Germany, 1988     

Relatively pseudocomplemented semilattices amalgamate strongly

Letk be any finite or infinite cardinal andS _ω the symmetric group of denumerable infinite degree. It is shown that fori<k ifG _i is thei-th row of a matrix whose columns are allk-termed sequences of elements ofS _ω in each of which all but a finite number of terms are equal to the identity ofS _ω thenG _i 's (withG _i ⁻¹ 's defined in an obvious way and with coordinatewise multiplication amongG _i 's andG _i ⁻¹'s) generate the Free Group onk free generatorsG _i . Analogously, Free Abelian and other types of free groups are also constructed. Presented by L. Fuchs.     

A Sharp Exponent Bound for McFarland Difference Sets withp=2

We show that under the self-conjugacy condition a McFarland difference set withp=2 andf2 in an abelian groupGcan only exist, if the exponent of the Sylow 2-subgroup does not exceed 4. The method also works for oddp(where the exponent bound ispand is necessary and sufficient), so that we obtain a unified proof of the exponent bounds for McFarland difference sets. We also correct a mistake in the proof of an exponent bound for (320, 88, 24)-difference sets in a previous paper.     

On the maximal number of certain subgraphs inK r -free graphs

Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T ₂(n)), whereT ₂(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK _r -free graphG withn vertices. In particular, in the class of allK _r -free graphs withn vertices the complete balanced (r – 1)-partite graphT _r–1(n) has the largest number of subgraphs isomorphic toK _t (t < r),C ₄,K _2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday