On Finite p-Groups Whose IA-Automorphisms Are All Class Preserving

Let G be a finite non-abelian p-group, where p is a prime. An automorphism α of G is called a class preserving automorphism if α(x) ∈ x ^G the conjugacy class of x in G, for all x ∈ G. An automorphism α of G is called an IA-automorphism if x ^?1α(x) ∈ G′ for each x ∈ G. In this paper, we give necessary and sufficient conditions on finite p-group G of nilpotency class 2 such that every IA-automorphism is class preserving.     

Reductions of 3-connected graphs with minimum degree at least four

We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x₁, x₂, x₃, x₄} and x₁x₂, x₃x₄ ∈ E(G) such that the graph (G ? x)/x₁x₂/x₃x₄ obtained by contraction of edges x₁x₂ and x₃x₄ in G – x is a 3-connected graph of minimum degree at least 4.

Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions.     

Optimal Subgroups and Applications to Nilpotent Elements

Let G be a reductive group acting on an affine variety X, let x ∈ X be a point whose G-orbit is not closed, and let S be a G-stable closed subvariety of X which meets the closure of the G-orbit of x but does not contain x. In this paper we study G. R. Kempf’s optimal class Ω _G (x; S) of cocharacters of G attached to the point x; in particular, we consider how this optimality transfers to subgroups of G. Suppose K is a G-completely reducible subgroup of G which fixes x, and let H = C _G (K)⁰. Our main result says that the H-orbit of x is also not closed, and the optimal class Ω _H (x; S) for H simply consists of the cocharacters in Ω _G (x; S) which evaluate in H. We apply this result in the case that G acts on its Lie algebra via the adjoint representation to obtain some new information about cocharacters associated with nilpotent elements in good characteristic.     

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     

A remark on divisibility of definable groups

We show that if G is a definably compact, definably connected definable group defined in an arbitrary o‐minimal structure, then G is divisible. Furthermore, if G is defined in an o‐minimal expansion of a field, k ∈ ? and p_k : G → G is the definable map given by p_k (x ) = x^k for all x ∈ G , then we have |(p_k )^–1(x )| ≥ k^r for all x ∈ G , where r > 0 is the maximal dimension of abelian definable subgroups of G . (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Path decompositions of multigraphs

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and μ(x) respectively. Define Ø(x) = the least even integer ≥ μ(x), if d(x) is even, the least odd integer ≥ μ(x), if d(x) is odd. In this paper it is shown that every multigraph G admits a faithful path decomposition—a partition P of the edges of G into simple paths such that every vertex x of G is an end of exactly Ø(x) paths in P. This result generalizes Lovász's path decomposition theorem, Li's perfect path double cover theorem (conjectured by Bondy), and a result of Fan concerning path covers of weighted graphs. It also implies an upper bound on the number of paths in a minimum path decomposition of a multigraph, which motivates a generalization of Gallai's path decomposition conjecture. © 1995 John Wiley & Sons, Inc.     

On the Marginal Automorphisms of a Group

Let W be a nonempty subset of a free group. We call an automorphism α of a group G a marginal automorphism if x ^?1α(x) ∈ W*(G) for each x ∈ G, where W*(G) is the marginal subgroup of G. In this article, we give some results on marginal automorphisms of a group.     

A sufficient condition for equality of edge-connectivity and minimum degree of a graph

Let G be a connected graph of order p ≥ 2, with edge-connectivity κ₁(G) and minimum degree δ(G). It is shown her ethat in order to obtain the equality κ₁(G) = δ(G), it is sufficient that, for each vertex x of minimum degree in G, the vertices in the neighbourhood N(x) of x have sufficiently large degree sum. This result implies a previous result of Chartrand, which required that δ(G) ≥ [p/2].     

A degree sum condition for longest cycles in 3‐connected graphs

For a graph G, we denote by d_G(x) and κ(G) the degree of a vertex x in G and the connectivity of G, respectively. In this article, we show that if G is a 3‐connected graph of order n such that d_G(x) + d_G(y) + d_G(z) ≥ d for every independent set {x, y, z}, then G contains a cycle of length at least min{d ? κ(G), n}. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 277–283, 2007     

A note on the line-distinguishing chromatic number and the chromatic index of a graph

Let λ(G) be the line-distinguishing chromatic number and x′(G) the chromatic index of a graph G. We prove the relation λ(G) ≥ x′(G), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.     

A New Result on Alspach's Problem

Let G be a simple graph. Let g(x) and f(x) be integer-valued functions defined on V(G) with g(x)≥2 and f(x)≥5 for all x∈V(G). It is proved that if G is an (mg+m−1, mf−m+1)-graph and H is a subgraph of G with m edges, then there exists a (g,f)-factorization of G orthogonal to H. Received: January 19, 1996 Revised: November 11, 1996     

Changing and unchanging of the domination number of a graph

Let G be a graph and γ(G) denote the domination number of G. A dominating set D of a graph G with |D|=γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-fixed if x belongs to every γ-set, (ii) γ-free if x belongs to some γ-set but not to all γ-sets, (iii) γ-bad if x belongs to no γ-set, (iv) γ^--free if x is γ-free and γ(G-x)=γ(G)-1, (v) γ⁰-free if x is γ-free and γ(G-x)=γ(G), and (vi) γ^q-fixed if x is γ-fixed and γ(G-x)=γ(G)+q. In this paper we investigate for any vertex x of a graph G whether x is γ^q-fixed, γ⁰-free, γ^--free or γ-bad when G is modified by deleting a vertex or adding or deleting an edge.     

Unfused Involutions in Finite Groups

ABSTRACT

Let x be a p-element of a finite group G. We say that x is unfused in G if, for some Sylow p-subgroup S of G containing x, all G-conjugates of x in S are S-conjugates. It is shown (using the classification of finite simple groups) that a finite group that contains an unfused involution has a chief factor of order 2.

     

Cohen-macaulay bipartite graphs

Let G be a graph on the vertex set V={x ₁, ..., x _n}. Let k be a field and let R be the polynomial ring k[x ₁, ..., x _n]. The graph ideal I(G), associated to G, is the ideal of R generated by the set of square-free monomials x _ix_j so that x _i, is adjacent to x _j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring. Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs. Partially supported by COFAA-IPN, CONACyT and SNI, México.     

Hamiltonism and Partially Square Graphs

 Given a graph G, we define its partially square graph G ^* as the graph obtained by adding edges uv whenever the vertices u and v have a common neighbor x satisfying the condition N _G[x]⊆N _G[u]∪N _G [v], where N _G[x]=N _G(x)∪{x}. In particular, this condition is satisfied if x does not center a claw (an induced K _1,3). Obviously G⊆G ^*⊆G ², where G ² is the square of G. We prove that a k-connected graph (k≥2) G is hamiltonian if the independence number α(G ^*) of G ^* does not exceed k. If we replace G ^* by G we get a well known result of Chvátal and Erdo?s. If G is claw-free and G ^* is replaced by G ² then we obtain a result of Ainouche, Broersma and Veldman. Relationships between connectivity of G and independence number of G ^* for other hamiltonian properties are also given in this paper. Received: June 17, 1996 Revised: October 30, 1998     

On Infinite Camina Groups

A group G is called a Camina group if G′ ≠ G and each element x ∈ G?G′ satisfies the equation x ^G  = xG′, where x ^G denotes the conjugacy class of x in G. Finite Camina groups were introduced by Alan Camina in 1978, and they had been studied since then by many authors. In this article, we start the study of infinite Camina groups. In particular, we characterize infinite Camina groups with a finite G′ (see Theorem 3.1) and we show that infinite non-abelian finitely generated Camina groups must be nonsolvable (see Theorem 4.3). We also describe locally finite Camina groups, residually finite Camina groups (see Section 3) and some periodic solvable Camina groups (see Section 5).     

A Property About Minimum Edge- and Minimum Clique-Cover of a Graph

 Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ ⁿ :Ex≤1,x≥0}, P(C)={x∈ℜ ⁿ :Cx≤1,x≥0}, α _E (G)=max{1 ^T x subject to x∈P(E)}, and α _C (G)= max{1 ^T x subject to x∈P(C)}. In this paper we prove that if α _E (G)=α _C (G), then γ(G)=θ(G). Received: May 20, 1998?Final version received: April 12, 1999     

The road-colouring problem

LetG be a finite directed graph which is irreducible and aperiodic. Assume each vertex ofG leads to at least two other vertices, and assumeG has a cycle of prime length which is a proper subset ofG. Then there exist two functionsr:G →G andb:G →G such that ifr(x)=y andb(x)=z thenx →y andx →z inG andy ≠z and such that some composition ofr’s andb’s is a constant function. This work was supported in part by the Natural Sciences and Engineering Research Council of Canada. I am grateful to Cornell University whose kind hospitality I enjoyed while working on this problem.     

Some Properties of Certain Subgroups of Tensor Squares of p-Groups

Let G be a finite p-group of order p ⁿ and ?(G) be the subgroup of the tensor square of G generated by all symbols x ? x, for all x in G. In the present article, we construct an upper bound for the order of ?(G) and any extra special p-group. It is also shown that ?(G) ? ?(G/G′). Using our result, we obtain the explicit structure of the tensor square of G and π₃ SK(G, 1). Finally, the structure of G will be characterized when the bound is attained.     

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