A Decomposition Theorem for Group Representations

In this paper we establish a decomposition theorem for an ordinary representation of a finite group G in any category C{\mathcal C} which expresses a suitable irreducible representation of G as the tensor product of two projective ones. The celebrated theorem due to Clifford for a linear representation turns out to be a particular case of it. For that purpose, a definition of projective extension of an ordinary representation of a normal subgroup of G is introduced, as well as a tensor product between two of them.     

Category of G-Groups and its Spectral Category

Let G be a group. We analyse some aspects of the category G-Grp of G-groups. In particular, we show that a construction similar to the construction of the spectral category, due to Gabriel and Oberst, and its dual, due to the second author, is possible for the category G-Grp.     

Clique percolation

Derényi, Palla and Vicsek introduced the following dependent percolation model, in the context of finding communities in networks. Starting with a random graph Ggenerated by some rule, form an auxiliary graph G′ whose vertices are the k‐cliques of G, in which two vertices are joined if the corresponding cliques share k – 1 vertices. They considered in particular the case where G = G(n,p), and found heuristically the threshold function p = p(n) above which a giant component appears in G′. Here we give a rigorous proof of this result, as well as many extensions. The model turns out to be very interesting due to the essential global dependence present in G′. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On a Commuting Graph on Conjugacy Classes of Groups

We consider the graph Γ(G), associated with the conjugacy classes of a group G. Its vertices are the nontrivial conjugacy classes of G, and we join two different classes C, D, whenever there exist x ∈ G and y ∈ D such that xy = yx. The aim of this article is twofold. First, we investigate which graphs can occur in various contexts and second, given a graph Γ(G) associated with G, we investigate the possible structure of G. We proved that if G is a periodic solvable group, then Γ(G) has at most two components, each of diameter at most 9. If G is any locally finite group, then Γ(G) has at most 6 components, each of diameter at most 19. Finally, we investigated periodic groups G with Γ(G) satisfying one of the following properties: (i) no edges exist between noncentral conjugacy classes, and (ii) no edges exist between infinite conjugacy classes. In particular, we showed that the only nonabelian groups satisfying (i) are the three finite groups of order 6 and 8.     

Matching behaviour is asymptotically normal

Ak-matching in a graphG is a set ofk edges, no two of which have a vertex in common. The number of these inG is writtenp(G, k). Using an idea due to L. H. Harper, we establish a condition under which these numbers are approximately normally distributed. We show that our condition is satisfied ifn=|V(G)| is large compared to the maximum degree Δ of a vertex inG(i.e. Δ=o(n)) orG is a large complete graph. One corollary of these results is that the number of points fixed by a randomly chosen involution in the symmetric groupS is asymptotically normally distributed.     

A decomposition theorem for G-groups

Some classical results about linear representations of a finite group G have been also proved for representations of G on non-abelian groups （G-groups）. In this paper we establish a decomposition theorem for irreducible G-groups which expresses a suitable irreducible G-group as a tensor product of two projective G-groups in a similar way to the celebrated theorem of Clifford for linear representations. Moreover, we study the non-abelian minimal normal subgroups of G in which this decomposition is possible.     

Non-Nilpotent Graph of a Group

We associate a graph 𝒩 _G with a group G (called the non-nilpotent graph of G) as follows: take G as the vertex set and two vertices are adjacent if they generate a non-nilpotent subgroup. In this article, we study the graph theoretical properties of 𝒩 _G and its induced subgraph on G \ nil(G), where nil(G) = {x ∈ G | ? x, y ? is nilpotent for all y ∈ G}. For any finite group G, we prove that 𝒩 _G has either |Z*(G)| or |Z*(G)| +1 connected components, where Z*(G) is the hypercenter of G. We give a new characterization for finite nilpotent groups in terms of the non-nilpotent graph. In fact, we prove that a finite group G is nilpotent if and only if the set of vertex degrees of 𝒩 _G has at most two elements.     

The nonorientable genus is additive

A graph G is a k-amalgamation of two graphs G₁ and G₂ if G = G₁ ∪ G₂ and G₁ ∩G₂ is a set of k vertices. In this paper we show that γ(G) differs from γ(G₁) + γ(G₂) by at most a quadratic on k, where γ denotes the nonorientable genus of a graph. In the sequel to this paper we show that no such bound holds for the orientable genus of k-amalgamations.     

The spread of the unicyclic graphs

Let G be a simple connected graph with n vertices and n edges which we call a unicyclic graph. In this paper, we first investigate the least eigenvalue λ_n(G), then we present two sharp bounds on the spread s(G) of G.     

On the Hopficity of HNN-Extensions of Polycyclic Groups

For a group G, an HNN-extension of polycyclic groups, we give two necessary and sufficient conditions for G to be hopfian. One is based on the nature of the endomorphism of G and the other on the nature of the associated subgroups of G. At the end, we give an application for HNN-extensions of nilpotent groups.     

Average distance and maximum induced forest

With the help of the Graffiti system, Fajtlowicz conjectured around 1992 that the average distance between two vertices of a connected graph G is at most half the maximum order of an induced bipartite subgraph of G, denoted α₂(G). We prove a strengthening of this conjecture by showing that the average distance between two vertices of a connected graph G is at most half the maximum order of an induced forest, denoted F(G). Moreover, we characterize the graphs maximizing the average distance among all graphs G having a fixed number of vertices and a fixed value of F(G) or α₂(G). Finally, we conjecture that the average distance between two vertices of a connected graph is at most half the maximum order of an induced linear forest (where a linear forest is a union of paths). © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 31–54, 2009     

The co-degrees of irreducible characters

LetG be a finite group. The co-degree of an irreducible character χ ofG is defined to be the number |G|/χ(1). The set of all prime divisors of all the co-degrees of the nonlinear irreducible characters ofG is denoted by Σ(G). First we show that Σ(G)=π(G) (the set of all prime divisors of |G|) unlessG is nilpotent-by-abelian. Then we make Σ(G) a graph by adjoining two elements of Σ(G) if and only if their product divides a co-degree of some nonlinear character ofG. We show that the graph Σ(G) is connected and has diameter at most 2. Additional information on the graph is given. These results are analogs to theorems obtained for the graph corresponding to the character degrees (by Manz, Staszewski, Willems and Wolf) and for the graph corresponding to the class sizes (by Bertram, Herzog and Mann). Finally, we investigate groups with some restriction on the co-degrees. Among other results we show that ifG has a co-degree which is ap-power for some primep, then the corresponding character is monomial andO _p (G)≠1. Also we describe groups in which each co-degree of a nonlinear character is divisible by at most two primes. These results generalize results of Chillag and Herzog. Other results are proved as well. The paper was written during this author’s visit at the Technion and the University of Tel Aviv. He would like to thank the departments of mathematics at the Technion and the University of Tel Aviv for their hospitality and support.     

On graphs determining links with maximal number of components via medial construction

Let G be a connected plane graph, D(G) be the corresponding link diagram via medial construction, and μ(D(G)) be the number of components of the link diagram D(G). In this paper, we first provide an elementary proof that μ(D(G))≤n(G)+1, where n(G) is the nullity of G. Then we lay emphasis on the extremal graphs, i.e. the graphs with μ(D(G))=n(G)+1. An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from K₁ by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs.     

Einstein homogeneous bisymmetric fibrations

We consider a homogeneous fibration G/L → G/K, with symmetric fiber and base, where G is a compact connected semisimple Lie group and L has maximal rank in G. We suppose the base space G/K is isotropy irreducible and the fiber K/L is simply connected. We investigate the existence of G-invariant Einstein metrics on G/L such that the natural projection onto G/K is a Riemannian submersion with totally geodesic fibers. These spaces are divided in two types: the fiber K/L is isotropy irreducible or is the product of two irreducible symmetric spaces. We classify all the G-invariant Einstein metrics with totally geodesic fibers for the first type. For the second type, we classify all these metrics when G is an exceptional Lie group. If G is a classical Lie group we classify all such metrics which are the orthogonal sum of the normal metrics on the fiber and on the base or such that the restriction to the fiber is also Einstein.     

Cyclic coloration of 3-polytopes

A cyclic coloration of a planar graph G is an assignment of colors to the points of G such that for any face bounding cycle the points of F have different colors. We observe that the upper bound 2ρ*(G), due to O. Ore and M. D. Plummer, can be improved to ρ*(G) + 9 when G is 3-connected (ρ* denotes the size of a maximum face). The proof uses two principal tools: the theory of Euler contributions and recent results on contractible lines in 3-connected graphs by K. Ando, H. Enomoto and A. Saito.     

Upper Bounds for the Rainbow Connection Numbers of Line Graphs

A path in an edge-colored graph G, where adjacent edges may be colored the same, is called a rainbow path if no two edges of it are colored the same. A nontrivial connected graph G is rainbow connected if for any two vertices of G there is a rainbow path connecting them. The rainbow connection number of G, denoted rc(G), is defined as the smallest number of colors such that G is rainbow connected. In this paper, we mainly study the rainbow connection number rc(L(G)) of the line graph L(G) of a graph G which contains triangles. We get two sharp upper bounds for rc(L(G)), in terms of the number of edge-disjoint triangles of G. We also give results on the iterated line graphs.     

Partitioning 2‐Edge‐Colored Ore‐Type Graphs by Monochromatic Cycles

Consider a graph G on n vertices satisfying the following Ore‐type condition: for any two nonadjacent vertices x and y of G, we have . We conjecture that if we color the edges of G with two colors then the vertex set of G can be partitioned to two vertex disjoint monochromatic cycles of distinct colors. In this article, we prove an asymptotic version of this conjecture.     

Hitting times for random walks on subdivision and triangulation graphs

Let G be a connected graph. The subdivision graph of G, denoted by S(G), is the graph obtained from G by inserting a new vertex into every edge of G. The triangulation graph of G, denoted by R(G), is the graph obtained from G by adding, for each edge uv, a new vertex whose neighbours are u and v. In this paper, we first provide complete information for the eigenvalues and eigenvectors of the probability transition matrix of a random walk on S(G) (res. R(G)) in terms of those of G. Then we give an explicit formula for the expected hitting time between any two vertices of S(G) (res. R(G)) in terms of those of G. Finally, as applications, we show that, the relations between the resistance distances, the number of spanning trees and the multiplicative degree-Kirchhoff index of S(G) (res. R(G)) and G can all be deduced from our results directly.     

A condition on finitely generated soluble groups

In this note we show that if Gis a finitely generated soluble group, then every infinite subset of Gcontains two elements generating a nilpotent group of class at most kif and only if Gis finite by a group in which every two generator subgroup is nilpotent of class at most k.