Commutativity Pattern of Finite Non-Abelian p-Groups Determine Their Orders

Let G be a non-abelian group and Z(G) be the center of G. Associate a graph Γ _G (called noncommuting graph of G) with G as follows: Take G?Z(G) as the vertices of Γ _G , and join two distinct vertices x and y, whenever xy ≠ yx. Here, we prove that “the commutativity pattern of a finite non-abelian p-group determine its order among the class of groups"; this means that if P is a finite non-abelian p-group such that Γ _P  ? Γ _H for some group H, then |P| = |H|.     

Non-Commuting Graphs of Nilpotent Groups

Let G be a non-abelian group and Z(G) be the center of G. The non-commuting graph Γ _G associated to G is the graph whose vertex set is G?Z(G) and two distinct elements x, y are adjacent if and only if xy ≠ yx. We prove that if G and H are non-abelian nilpotent groups with irregular isomorphic non-commuting graphs, then |G| = |H|.     

Noncyclic Graph of a Group

We associate a graph Γ _G to a nonlocally cyclic group G (called the noncyclic graph of G) as follows: take G\ Cyc(G) as vertex set, where Cyc(G) = {x ? G| 〈x, y〉 is cyclic for all y ? G}, and join two vertices if they do not generate a cyclic subgroup. We study the properties of this graph and we establish some graph theoretical properties (such as regularity) of this graph in terms of the group ones. We prove that the clique number of Γ _G is finite if and only if Γ _G has no infinite clique. We prove that if G is a finite nilpotent group and H is a group with Γ _G  ? Γ _H and |Cyc(G)| = |Cyc(H)| = 1, then H is a finite nilpotent group. We give some examples of groups G whose noncyclic graphs are “unique”, i.e., if Γ _G  ? Γ _H for some group H, then G ? H. In view of these examples, we conjecture that every finite nonabelian simple group has a unique noncyclic graph. Also we give some examples of finite noncyclic groups G with the property that if Γ _G  ? Γ _H for some group H, then |G| = |H|. These suggest the question whether the latter property holds for all finite noncyclic groups.     

A new characterization of L 2(q) by its noncommuting graph

Let G be a non-abelian group and associate a non-commuting graph ∇(G) with G as follows: the vertex set of ∇(G) is G\Z(G) with two vertices x and y joined by an edge whenever the commutator of x and y is not the identity. In this short paper we prove that if G is a finite group with ∇(G) ≅ ∇(M), where M = L ₂(q) (q = p ⁿ , p is a prime), then G ≅ M.      

The non-isolated vertices in the generating graph of a direct powers of simple groups

For a finite group G let Γ(G) denote the graph defined on the non-identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. Many deep results on the generation of the finite simple groups G can be equivalently stated as theorems that ensure that Γ(G) is a rich graph, with several good properties. In this paper we want to consider Γ(G ^δ ) where G is a finite non-abelian simple group and G ^δ is the largest 2-generated power of G, with the aim to investigate whether the good generation properties of G still affect the behaviour of Γ(G ^δ ). In particular we prove that the graph obtained from Γ(G ^δ ) by removing the isolated vertices is 1-arc transitive and connected and we investigate the diameter of this graph. Moreover, some intriguing open questions will be introduced and their solutions will be exemplified for $G=\operatorname{Alt}(5)$ .     

Characterization of $ {\mathbb{A}_{16}} $ by a noncommuting graph

Let G be a finite non-Abelian group. We define a graph Γ _G ; called the noncommuting graph of G; with a vertex set G − Z(G) such that two vertices x and y are adjacent if and only if xy ≠ yx: Abdollahi, Akbari, and Maimani put forward the following conjecture (the AAM conjecture): If S is a finite non-Abelian simple group and G is a group such that Γ _S ≅ Γ _G ; then S ≅ G: It is still unknown if this conjecture holds for all simple finite groups with connected prime graph except \mathbbA₁₀ {\mathbb{A}_{10}} , L ₄(8), L ₄(4), and U ₄(4). In this paper, we prove that if \mathbbA₁₆ {\mathbb{A}_{16}} denotes the alternating group of degree 16; then, for any finite group G; the graph isomorphism G_\mathbbA16 @ G_G {\Gamma_{{\mathbb{A}_{16}}}} \cong {\Gamma_G} implies that \mathbbA₁₆ @ G {\mathbb{A}_{16}} \cong G .     

A finiteness theorem for primal extensions

A set W⊆V(G) is called homogeneous in a graph G if 2?|W|?|V(G)|-1, and N(x)?W=N(y)?W for each x,y∈W. A graph without homogeneous sets is called prime. A graph H is called a (primal) extension of a graph G if G is an induced subgraph of H, and H is a prime graph. An extension H of G is minimal if there are no extensions of G in the set ISub(H)?{H}. We denote by Ext(G) the set of all minimal extensions of a graph G.We investigate the following problem: find conditions under which Ext(G) is a finite set. The main result of Giakoumakis (Discrete Math. 177 (1997) 83-97) is the following sufficient condition.

Theorem. If every homogeneous set of G has exactly two vertices thenExt(G)is a finite set.     

A note on Z 3-connected graphs with degree sum condition

A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al.     

Max-min of polynomials and exponential diophantine equations

In this paper we study the maximum-minimum value of polynomials over the integer ring Z. In particular, we prove the following: Let F(x,y) be a polynomial over Z. Then, maxx∈Z(T)miny∈Z|F(x,y)|=o(T1/2) as T→∞ if and only if there is a positive integer B such that maxx∈Zminy∈Z|F(x,y)|?B. We then apply these results to exponential diophantine equations and obtain that: Let f(x,y), g(x,y) and G(x,y) be polynomials over Q, G(x,y)∈(Q[x,y]−Q[x])∪Q, and b a positive integer. For every α in Z, there is a y in Z such that f(α,y)+g(α,y)bG(α,y)=0 if and only if for every integer α there exists an h(x)∈Q[x] such that f(x,h(x))+g(x,h(x))bG(x,h(x))≡0, and h(α)∈Z.     

Some remarks on conjugate closed groups

Let G be a group. In this note we define conjugate closed groups, which are briefly called CC — Groups. These groups form a proper subclass of T — Groups. We prove that if G = Z(G) × H, then G is conjugate closed if and only if H is conjugate closed. We also show that a finite group G is semisimple, conjugate closed and perfect if and only if it is a direct product of non-abelian and simple groups.     

The total graph and regular graph of a commutative ring

Let R be a commutative ring. The total graph of R, denoted by T(Γ(R)) is a graph with all elements of R as vertices, and two distinct vertices x,y∈R, are adjacent if and only if x+y∈Z(R), where Z(R) denotes the set of zero-divisors of R. Let regular graph of R, Reg(Γ(R)), be the induced subgraph of T(Γ(R)) on the regular elements of R. Let R be a commutative Noetherian ring and Z(R) is not an ideal. In this paper we show that if T(Γ(R)) is a connected graph, then . Also, we prove that if R is a finite ring, then T(Γ(R)) is a Hamiltonian graph. Finally, we show that if S is a commutative Noetherian ring and Reg(S) is finite, then S is finite.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

The strong chromatic index of a class of graphs

The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ^′(G)≤6. Let H₀ be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H₀ and d(x)+d(y)≤5 for any edge xy of G then sχ^′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.     

Simple exceptional groups of Lie type are determined by their character degrees

Let G be a finite group. Denote by Irr(G) the set of all irreducible complex characters of G. Let cd(G)={c(1)  |  c ? Irr(G)}{{\rm cd}(G)=\{\chi(1)\;|\;\chi\in {\rm Irr}(G)\}} be the set of all irreducible complex character degrees of G forgetting multiplicities, and let X₁(G) be the set of all irreducible complex character degrees of G counting multiplicities. Let H be any non-abelian simple exceptional group of Lie type. In this paper, we will show that if S is a non-abelian simple group and cd(S) í cd(H){{\rm cd}(S)\subseteq {\rm cd}(H)} then S must be isomorphic to H. As a consequence, we show that if G is a finite group with X₁(G) í X₁(H){{\rm X}_1(G)\subseteq {\rm X}_1(H)} then G is isomorphic to H. In particular, this implies that the simple exceptional groups of Lie type are uniquely determined by the structure of their complex group algebras.     

On intransitive graph-restrictive permutation groups

Let Γ be a finite connected G-vertex-transitive graph and let v be a vertex of Γ. If the permutation group induced by the action of the vertex-stabiliser G _v on the neighbourhood Γ(v) is permutation isomorphic to L, then (Γ,G) is said to be locally L. A permutation group L is graph-restrictive if there exists a constant c(L) such that, for every locally L pair (Γ,G) and a vertex v of Γ, the inequality |G _v |≤c(L) holds. We show that an intransitive group is graph-restrictive if and only if it is semiregular.     

Connectivity in digraphs

Let c(x,y) denote the maximum number of edge-disjoint directed paths joining x to y in the digraph G. It is shown that, for a given point a of G, c(a,x) ≤ c(x,a) for any x implies that the outdegree of a is ≤ its indegree. An immediate consequence is Kotzig's conjecture: Given a digraph G, c(x,y) = c(y,x) for every x, y if and only if the graph is pseudo-symmetric, i.e., each point has the same indegree and outdegree (the “if” part having been proved by Kotzig). The same method is applied to prove a weakened form of a conjecture of N. Robertson, while the original conjecture is disproved.     

Zero-divisor graphs, von Neumann regular rings, and Boolean algebras

For a commutative ring R with set of zero-divisors Z(R), the zero-divisor graph of R is Γ(R)=Z(R)−{0}, with distinct vertices x and y adjacent if and only if xy=0. In this paper, we show that Γ(T(R)) and Γ(R) are isomorphic as graphs, where T(R) is the total quotient ring of R, and that Γ(R) is uniquely complemented if and only if either T(R) is von Neumann regular or Γ(R) is a star graph. We also investigate which cardinal numbers can arise as orders of equivalence classes (related to annihilator conditions) in a von Neumann regular ring.     

On <Emphasis Type="Italic">r</Emphasis>-recognition by prime graph of <Emphasis Type="Italic">B</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>(3) where <Emphasis Type="Italic">p</Emphasis> is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then \({G\cong B_p(3)}\) or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then \({G\cong B_3(3), C_3(3), D_4(3)}\), or \({G/O_2(G)\cong {\rm Aut}(^2B_2(8))}\). As a corollary, the main result of the above paper is obtained.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.