On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

Finite <Emphasis Type="Italic">p</Emphasis>-central groups of height <Emphasis Type="Italic">k</Emphasis>

A finite group G is called p ⁱ -central of height k if every element of order p ⁱ of G is contained in the k ^th -term ζ _k (G) of the ascending central series of G. If p is odd, such a group has to be p-nilpotent (Thm. A). Finite p-central p-groups of height p − 2 can be seen as the dual analogue of finite potent p-groups, i.e., for such a finite p-group P the group P/Ω₁(P) is also p-central of height p − 2 (Thm. B). In such a group P, the index of P ^p is less than or equal to the order of the subgroup Ω₁(P) (Thm. C). If the Sylow p-subgroup P of a finite group G is p-central of height p − 1, p odd, and N _G (P) is p-nilpotent, then G is also p-nilpotent (Thm. D). Moreover, if G is a p-soluble finite group, p odd, and P ∈ Syl _p (G) is p-central of height p − 2, then N _G (P) controls p-fusion in G (Thm. E). It is well-known that the last two properties hold for Swan groups (see [11]).     

Distributivity conditions for lattices of dominions in quasivarieties of Abelian groups

Let ℳ be any quasivariety of Abelian groups, L_q(ℳ) be a subquasivariety lattice of ℳ, dom _G ^ℳ be the dominion of a subgroup H of a group G in ℳ, and G/dom _G ^ℳ (H) be a finitely generated group. It is known that the set L(G, H, ℳ) = {dom _G ^N (H)| N ∈ L_q(ℳ)} forms a lattice w.r.t. set-theoretic inclusion. We look at the structure of dom _G ^ℳ (H). It is proved that the lattice L(G,H,ℳ) is semidistributive and necessary and sufficient conditions are specified for its being distributive. __________ Translated from Algebra i Logika, Vol. 45, No. 4, pp. 484–499, July–August, 2006.     

Omega subgroups of powerful <Emphasis Type="Italic">p</Emphasis>-groups

Let G be a powerful finite p-group. In this note, we give a short elementary proof of the following facts for all i ≥ 0: (i) exp Ω_i(G) ≤ p ⁱ for odd p, and expΩ_i(G) ≤ 2 ⁱ⁺¹ for p = 2; (ii) the index |G: G ^{p i}| coincides with the number of elements of G of order at most p ⁱ. Supported by the Spanish Ministry of Science and Education, grant MTM2004-04665, partly with FEDER funds, and by the University of the Basque Country, grant UPV05/99.     

Disjoint homotopic paths and trees in a planar graph

In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ², a subset {I ₁, …,I _p} of the faces ofG, and pathsC ₁, …,C _k inG, with endpoints on the boundary ofI ₁ ∪ … ∪I _p; find: pairwise disjoint simple pathsP ₁, …,P _k inG so that, for eachi=1, …,k, P _i is homotopic toC _i in the space ℝ²\(I ₁ ∪ … ∪I _p). Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ² and pairwise disjoint setsW ₁, …,W _k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT ₁, …,T _k ofG whereT _i (i=1, …, k).     

Onp-absolutely summing constants of banach spaces

Given 1≦p<∞ and a real Banach spaceX, we define thep-absolutely summing constantμ _p(X) as inf{Σ _i ^=1/m |x*(x _i)|^p p Σ _i ^=1/m ‖x _i‖^p p]¹ p}, where the supremum ranges over {x*∈X*; ‖x*‖≤1} and the infimum is taken over all sets {x ₁,x ₂, …,x _m} ⊂X such that Σ _i ^=1/m ‖x _i‖>0. It follows immediately from [2] thatμ _p(X)>0 if and only ifX is finite dimensional. In this paper we find the exact values ofμ _p(X) for various spaces, and obtain some asymptotic estimates ofμ _p(X) for general finite dimensional Banach spaces. This is a part of the author’s Ph.D. Thesis prepared at the Hebrew University of Jerusalem, under the supervision of Prof. A. Dvoretzky and Prof. J. Lindenstrauss.     

Some Results on p-Nilpotence and Supersolvability of Finite Groups

Let G be a finite group. A subgroup K of a group G is called an ?-subgroup of G if N _G (K) ∩ K ^x  ≦ K for all x ? G. The set of all ?-subgroups of G will be denoted by ?(G). Let P be a nontrivial p-group. A chain of subgroups 1 = P ₀ ? P ₁ ? ··· ? P _n  = P is called a maximal chain of P provided that |P _i : P _i?1| = p, i = 1, 2, ···, n. A nontrivial p-subgroup P of G is called weakly supersolvably embedded in G if P has a maximal chain 1 = P ₀ ? P ₁ ? ··· ? P _i  ? ··· ? P _n  = P such that P _i  ? ?(G) for i = 1, 2, ···, n. Using the concept of weakly supersolvably embedded, we obtain new characterizations of p-nilpotent and supersolvable finite groups.     

Finite groups with some CAP-subgroups

Let G be a finite group. A subgroup H of G is called a CAP-subgroup if the following condition is satisfied: for each chief factor K/L of G either HK = HL or H ∩ K = H ∩ L. Let p be a prime factor of |G| and let P be a Sylow p-subgroup of G. If d is the minimum number of generators of P then there exists a family of maximal subgroups of P, denoted by M _d (P)={P ₁, P ₂,…, P _d } such that ∩ _i=1 ^d P _i = ?(P). In this paper, we investigate the group G satisfying the condition: every member of a fixed M _d (P) is a CAP-subgroup of G. For example, if, in addition, G is p-solvable, then G is p-supersolvable.     

Degree Sums,Connectivity and Dominating Cycles in Graphs

Let G be a graph of order n with connectivity κ≥3 and let α be the independence number of G. Set σ₄(G)= min{∑⁴ _{i =1} d(x _i ):{x ₁,x ₂,x ₃,x ₄} is an independent set of G}. In this paper, we will prove that if σ₄(G)≥n+2κ, then there exists a longest cycle C of G such that V(G−C) is an independent set of G. Furthermore, if the minimum degree of G is at least α, then G is hamiltonian. Received: July 31, 1998?Final version received: October 4, 2000     

Transfers of metabelian p-groups

Explicit expressions for the transfers V _i from a metabelian p-group G of coclass cc(G) = 1 to its maximal normal subgroups M ₁, . . . , M _p+1 are derived by means of relations for generators. The expressions for the exceptional case p = 2 differ significantly from the standard case of odd primes p ≥ 3. In both cases the transfer kernels Ker(V _i ) are calculated and the principalisation type of the metabelian p-group is determined, if G is realised as the Galois group Gal(F_p²(K)|K){{\rm{Gal}}({F}_p^2(K)\vert K)} of the second Hilbert p-class field F_p²(K){{F}_p^2(K)} of an algebraic number field K. For certain metabelian 3-groups G with abelianisation G/G′ of type (3, 3) and of coclass cc(G) = r ≥ 3, it is shown that the principalisation type determines the position of G on the coclass graph G(3,r){\mathcal{G}(3,r)} in the sense of Eick and Leedham-Green.     

Nonnormal and minimal nonabelian subgroups of a finite group

Let G be a finite p-group. If p = 2, then a nonabelian group G = Ω₁(G) is generated by dihedral subgroups of order 8. If p > 2 and a nonabelian group G = Ω₁(G) has no subgroup isomorphic to S_p²{\Sigma _{{p^2}}}, a Sylow p-subgroup of the symmetric group of degree p ², then it is generated by nonabelian subgroups of order p ³ and exponent p. If p > 2 and the irregular p-group G has < p nonabelian subgroups of order p ^p and exponent p, then G is of maximal class and order p ^p+1. We also study in some detail the p-groups, containing exactly p nonabelian subgroups of order p ^p and exponent p. In conclusion, we prove three new counting theorems on the number of subgroups of maximal class of certain type in a p-group. In particular, we prove that if p > 2, and G is a p-group of order > p ^p+1, then the number of subgroups ≅ ΣS_p²{\Sigma _{{p^2}}} in G is a multiple of p.     

Some results on the majorization theorem of connected graphs

Let π = (d ₁, d ₂, ..., d _n ) and π′ = (d′ ₁, d′ ₂, ..., d′ _n ) be two non-increasing degree sequences. We say π is majorizated by π′, denoted by π ⊲ π′, if and only if π ≠ π′, Σ _i=1 ⁿ d _i = Σ _i=1 ⁿ d′ _i , and Σ _i=1 ^j d _i ≤ Σ _i=1 ^j d′ _i for all j = 1, 2, ..., n. Weuse C _π to denote the class of connected graphs with degree sequence π. Let ρ(G) be the spectral radius, i.e., the largest eigenvalue of the adjacent matrix of G. In this paper, we extend the main results of [Liu, M. H., Liu, B. L., You, Z. F.: The majorization theorem of connected graphs. Linear Algebra Appl., 431(1), 553–557 (2009)] and [Bıyıkoğlu, T., Leydold, J.: Graphs with given degree sequence and maximal spectral radius. Electron. J. Combin., 15(1), R119 (2008)]. Moreover, we prove that if π and π′ are two different non-increasing degree sequences of unicyclic graphs with π ⊲ π′, G and G′ are the unicyclic graphs with the greatest spectral radii in C _π and C′ _π , respectively, then ρ(G) < ρ(G′).     

Longest Paths and Longest Cycles in Graphs with Large Degree Sums

 Let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle, respectively, of a finite, simple graph G. Define σ₄(G)=min{d(x ₁)+d(x ₂)+ d(x ₃)+d(x ₄) | {x ₁,…,x ₄} is independent in G}. In this paper, the difference p(G)−c(G) is considered for 2-connected graphs G with σ₄(G)≥|V(G)|+3. Among others, we show that p(G)−c(G)≤2 or every longest path in G is a dominating path. Received: August 28, 2000 Final version received: May 23, 2002     

The Roman <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f ₁, f ₂, …, f _d } of distinct Roman k-dominating functions on G with the property that Σ _i=1 ^d f _i (v) ≤ 2 for each v ∈ V (G), is called a Roman k-dominating family (of functions) on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by d _kR (G). Note that the Roman 1-domatic number d _1R (G) is the usual Roman domatic number d _R (G). In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for d _kR (G). In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.     

OD-characterization of Almost Simple Groups Related to U3（5）

Let G be a finite group with order ｜G｜=p1^α1p2^α2……pk^αk, where p1 〈 p2 〈……〈 Pk are prime numbers. One of the well-known simple graphs associated with G is the prime graph （or Gruenberg- Kegel graph） denoted .by г（G） （or GK（G））. This graph is constructed as follows： The vertex set of it is π（G） = {p1,p2,…,pk} and two vertices pi, pj with i≠j are adjacent by an edge （and we write pi - pj） if and only if G contains an element of order pipj. The degree deg（pi） of a vertex pj ∈π（G） is the number of edges incident on pi. We define D（G） ：= （deg（p1）, deg（p2）,..., deg（pk））, which is called the degree pattern of G. A group G is called k-fold OD-characterizable if there exist exactly k non- isomorphic groups H such that ｜H｜ = ｜G｜ and D（H） = D（G）. Moreover, a 1-fold OD-characterizable group is simply called OD-characterizable. Let L ：= U3（5） be the projective special unitary group. In this paper, we classify groups with the same order and degree pattern as an almost simple group related to L. In fact, we obtain that L and L.2 are OD-characterizable; L.3 is 3-fold OD-characterizable; L.S3 is 6-fold OD-characterizable.     

Normal <Emphasis Type="Italic">π</Emphasis>-complements for finite groups

Let G be a finite group. For a finite p-group P the subgroup generated by all elements of order p is denoted by Ω₁(p). Zhang [5] proved that if P is a Sylow p-subgroup of G, Ω₁(P) ≦ Z(P) and N _G (Z(P)) has a normal p-complement, then G has a normal p-complement. The object of this paper is to generalize this result. This paper was partly supported by Hungarian National Foundation for Scientific Research Grant # T049841 and T038059.     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

Elementary proof of a theorem of Blackburn

For a positive integer n, a finite p-group G is called an ℳ _n -group, if all subgroups of index p ⁿ of G are metacyclic, but there is at least one subgroup of index p ⁿ⁻¹ that is not. A classical result in p-group theory is the classification of ℳ₁-groups by Blackburn. In this paper, we give a slightly shorter and more elementary proof of this result.