Autocommuting probability of a finite group

Let G be a finite group and Aut(G) the automorphism group of G. The autocommuting probability of G, denoted by Pr(G,Aut(G)), is the probability that a randomly chosen automorphism of G fixes a randomly chosen element of G. In this paper, we study Pr(G,Aut(G)) through a generalization. We obtain a computing formula, several bounds and characterizations of G through Pr(G,Aut(G)). We conclude the paper by showing that the generalized autocommuting probability of G remains unchanged under autoisoclinism.     

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.     

On the differences between Szeged and Wiener indices of graphs

Let G be a connected graph and η(G)=Sz(G)−W(G), where W(G) and Sz(G) are the Wiener and Szeged indices of G, respectively. A well-known result of Klav?ar, Rajapakse, and Gutman states that η(G)≥0, and by a result of Dobrynin and Gutman η(G)=0 if and only if each block of G is complete. In this paper, a path-edge matrix for the graph G is presented by which it is possible to classify the graphs in which η(G)=2. It is also proved that there is no graph G with the property that η(G)=1 or η(G)=3. Finally, it is proved that, for a given positive integer k,k≠1,3, there exists a graph G with η(G)=k.     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

A generalization of a converse to Schur’s theorem

Niroomand (Arch. Math. 94 (2010) 401–404) proved a converse to a theorem of Schur in the following sense. He proved that if G is a group such that [G, G] is finite and G/Z(G) is finitely generated, then G/Z(G) is finite, of order bounded above by [G, G] ^k where k is the minimal number of generators required for G/Z(G). Here, we give a completely elementary short proof of a further generalization.     

Joint continuity of multiplication on the dual of the left uniformly continuous functions

Let G be a locally compact group and LUC(G) the C*-algebra of the bounded left uniformly continuous functions on G. The spectrum G ^LUC of LUC(G) is the universal semigroup compactification of G with respect to the joint continuity property: the multiplication on G×G ^LUC is jointly continuous. The paper studies the joint weak* continuity of multiplication on LUC(G)^* and, in particular, the question how the joint continuity property of G ^LUC can be related to a property concerning the whole algebra LUC(G)^*. The group G is naturally replaced by the measure algebra M(G), and LUC(G)^* can be identified with M(G ^LUC), the space of regular Borel measures on G ^LUC. It is shown that the joint weak* continuity can fail even on bounded sets of M(G)×M(G ^LUC), but, on the other hand, the multiplication on M(G)×M(G ^LUC) is positive continuous in the sense of Jewett.     

Vertex-switching,isomorphism, and pseudosimilarity

A vertex-switching G_s of a graph G is obtained by deleting from G all edges of G with exactly one end in the set of vertices S, and then adding to G all edges of the complement of G with exactly one end in S. We characterize the situations in which G_s is isomorphic to G, a result with application to the vertex-switching reconstruction problem. We use these results to construct pairs of vertex-switching pseudosimilar vertices, nonsimilar vertices u and v in a graph G with G_{u} isomorphic to G_{v}. We show that every such pair can be constructed by our methods.     

On Subgroups Generated by Small Classes in Finite Groups

Let G be a finite group and M(G) be the subgroup of G generated by all noncentral elements of G that lie in the conjugacy classes of the smallest size. Recently several results have been proved regarding the nilpotency class of M(G) and F(M(G)), where F(M(G)) denotes the Fitting subgroup of M(G). We prove some conditional results regarding the nilpotency class of M(G).     

Induced Matching Extendable Graph Powers

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. We obtain the following two results which give positive answers to two conjectures of Yuan. Result 1. If a connected graph G with |V(G)| even is locally connected, then G² is strongly IM-extendable. Result 2. If G is a 2-connected graph with |V(G)| even, then G³ is strongly IM-extendable. Research Supported by NSFC Fund 10371102.     

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 Edge Singularity and Eigenvectors of Mixed Graphs

Let G be a mixed glaph which is obtained from an undirected graph by orienting some of its edges. The eigenvalues and eigenvectors of G are, respectively, defined to be those of the Laplacian matrix L（G） of G. As L（G） is positive semidefinite, the singularity of L（G） is determined by its least eigenvalue λ1 （G）. This paper introduces a new parameter edge singularity εs（G） that reflects the singularity of L（G）, which is the minimum number of edges of G whose deletion yields that all the components of the resulting graph are singular. We give some inequalities between εs（G） and λ1 （G） （and other parameters） of G. In the case of εs（G） = 1, we obtain a property on the structure of the eigenvectors of G corresponding to λ1 （G）, which is similar to the property of Fiedler vectors of a simple graph given by Fiedler.     

Quasi-permutation Representations of the Groups SU (3, q2) and PSU (3, q2)

A square matrix over the complex field with non-negative integral trace is called a quasi-permutation matrix. For a finite group G the minimal degree of a faithful permutation representation of G is denoted by p(G). The minimal degree of a faithful representation of G by quasi-permutation matrices over the rational and the complex numbers are denoted by q(G) and c(G) respectively. Finally r(G) denotes the minimal degree of a faithful rational valued complex character of G. In this paper p(G), q(G), c(G) and r(G) are calculated for the groups PSU (3, q²) and SU (3, q²).AMS Subject Classification (2000): 20C15     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

Special representations of the group SP(4,q) with minimal degrees

Let G be a finite group. Let p(G) denote the minimal degree of a faithful permutation representation ofG and let q(G) and c(G) denote the minimal degree of a faithful representation of G by quasi-permutation matrices over the rational and the complex numbers, respectively. Finally r(G) denotes the minimal degree of a faithful rational valued complex character of G. The purpose of this paper is to calculate p(G), q(G), c(G) and r(G) for the group SP(4,q). This revised version was published online in June 2006 with corrections to the Cover Date.     

The genus of the 2-amalgamations of graphs

A graph G is called the 2-amalgamation of subgraphs G₁ and G₂ if G = G₁ ∪ G₂ and G₁ ∩ G₂ = {x, y}, 2 distinct points. in this case we write G = G₁∪_{{x, y}} G₂. in this paper we show that the orientable genus, γ(G), satisfies the inequalities γ(G₁) + γ(G₂) ? 1 ≤ γ(G₁ ∪_{{x, y}} G₂) ≤ γ(G₁) + γ(G₂) + 1 and that this is the best possible result, i. e., the resulting three values for γ(G₁ ∪_{{x, y}} G₂) which are possible can actually be realized by appropriate choices for G₁ and G₂.     

Commuting graphs of groups and related numerical parameters

Given a finite group G, we denote by Δ(G) the commuting graph of G which is defined as follows: the vertex set is G and two distinct vertices x and y are joined by an edge if and only if xy = yx. Clearly, Δ(G) is always connected for any group G. We denote by κ(G) the number of spanning trees of Δ(G). In the present paper, among other results, we first obtain the value κ(G) for some specific groups G, such as Frobenius groups, Dihedral groups, AC-groups, etc. Next, we characterize the alternating group A₅, in the class of nonsolvable groups through its tree-number κ(A₅). Finally, we classify the finite groups for which the power graph and the commuting graph coincide.     

Presentations for a class of generalized Thompson’s groups

For a given group G and a monomorphism φ:G→G×G there is a group ?_φ(G), introduced by the author, which blends Thompson’s group F with G. Given a presentation of G we determine a presentation of ?_φ(G). In particular, we prove that ?_φ(G) is finitely generated (resp. finitely presented) if G is finitely generated (resp. finitely presented).     

On Two Theorems of Finite Solvable Groups

For a finite group G, let T（G） denote a set of primes such that a prime p belongs to T（G） if and only if p is a divisor of the index of some maximal subgroup of G. It is proved that if G satisfies any one of the following conditions： （1） G has a p-complement for each p∈T（G）; （2）│T（G）│= 2： （3） the normalizer of a Sylow p-subgroup of G has prime power index for each odd prime p∈T（G）; then G either is solvable or G/Sol（G）≌PSL（2, 7） where Sol（G） is the largest solvable normal subgroup of G.     

Greatest common divisors and least common multiples of graphs

A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG ₁ andG ₂ ifG is a graph of maximum size for whichG|G ₁ andG|G ₂, while a graphH without isolated vertices is a least common multiple ofG ₁ andG ₂ ifH is a graph of minimum size for whichG ₁|H andG ₂|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG ₁ andG ₂ to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG ₁,G ₂ of graphs are determined, including when one ofG ₁ andG ₂ is a cycle of even length and the other is a star.G. C's research was supported in part by the Office of Naval Research, under Grant N00014-91-I-1060     

Adaptable chromatic number of graph products

A colouring of the vertices of a graph (or hypergraph) G is adapted to a given colouring of the edges of G if no edge has the same colour as both (or all) its vertices. The adaptable chromatic number of G is the smallest integer k such that each edge-colouring of G by colours 1,2,…,k admits an adapted vertex-colouring of G by the same colours 1,2,…,k. (The adaptable chromatic number is just one more than a previously investigated notion of chromatic capacity.) The adaptable chromatic number of a graph G is smaller than or equal to the ordinary chromatic number of G. While the ordinary chromatic number of all (categorical) powers G^k of G remains the same as that of G, the adaptable chromatic number of G^k may increase with k. We conjecture that for all sufficiently large k the adaptable chromatic number of G^k equals the chromatic number of G. When G is complete, we prove this conjecture with k≥4, and offer additional evidence suggesting it may hold with k≥2. We also discuss other products and propose several open problems.