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     

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.     

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.     

π-quasinormally embedded and c-supplemented subgroup of finite group

Suppose that H is a subgroup of a finite group G. H is called π-quasinormal in G if it permutes with every Sylow subgroup of G; H is called π-quasinormally embedded in G provided every Sylow subgroup of H is a Sylow subgroup of some π-quasinormal subgroup of G; H is called c-supplemented in G if there exists a subgroup N of G such that G = HN and H ∩ N ⩽ H _G = Core _G (H). In this paper, finite groups G satisfying the condition that some kinds of subgroups of G are either π-quasinormally embedded or c-supplemented in G, are investigated, and theorems which unify some recent results are given.      

On packing 3‐vertex paths in a graph

Let G be a connected graph and let eb(G) and λ(G) denote the number of end‐blocks and the maximum number of disjoint 3‐vertex paths Λ in G. We prove the following theorems on claw‐free graphs: (t1) if G is claw‐free and eb(G) ≤ 2 (and in particular, G is 2‐connected) then λ(G) = ⌊| V(G)|/3⌋; (t2) if G is claw‐free and eb(G) ≥ 2 then λ(G) ≥ ⌊(| V(G) | − eb(G) + 2)/3 ⌋; and (t3) if G is claw‐free and Δ^*‐free then λ(G) = ⌊| V(G) |/3⌋ (here Δ^* is a graph obtained from a triangle Δ by attaching to each vertex a new dangling edge). We also give the following sufficient condition for a graph to have a Λ‐factor: Let n and p be integers, 1 ≤ p ≤ n − 2, G a 2‐connected graph, and |V(G)| = 3n. Suppose that G − S has a Λ‐factor for every S ⊆ V(G) such that |S| = 3p and both V(G) − S and S induce connected subgraphs in G. Then G has a Λ‐factor. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 175–197, 2001     

Cross-sections, quotients, and representation rings of semisimple algebraic groups

Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny t:[^(G)] ? G \tau :\hat{G} \to G is bijective; this answers Grothendieck’s question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg’s theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G] ^G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G] ^G and that of the representation ring of G and answer two Grothendieck’s questions on constructing generating sets of k[G] ^G . We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T ⇢ G/T where T is a maximal torus of G and W the Weyl group.     

On a group with three supersolvable subgroups of pairwise relatively prime indices

In this paper, we show that if G is a finite group with three supersolvable subgroups of pairwise relatively prime indices in G and G′ is nilpotent, then G is supersolvable. Let π(G) denote the set of prime divisors of |G| and max(π(G)) denote the largest prime divisor of |G|. We also establish that if G is a finite group such that G has three supersolvable subgroups H, K, and L whose indices in G are pairwise relatively prime, q \nmid p-1{q \nmid p-1} where p =  max(π(G)) and q = max(π(L)) with L a Hall p′-subgroup of G, then G is supersolvable.     

A geometric approach to complete reducibility

Let G be a connected reductive linear algebraic group. We use geometric methods to investigate G-completely reducible subgroups of G, giving new criteria for G-complete reducibility. We show that a subgroup of G is G-completely reducible if and only if it is strongly reductive in G; this allows us to use ideas of R.W. Richardson and Hilbert–Mumford–Kempf from geometric invariant theory. We deduce that a normal subgroup of a G-completely reducible subgroup of G is again G-completely reducible, thereby providing an affirmative answer to a question posed by J.-P. Serre, and conversely we prove that the normalizer of a G-completely reducible subgroup of G is again G-completely reducible. Some rationality questions and applications to the spherical building of G are considered. Many of our results extend to the case of non-connected G. Mathematics Subject Classification (2000) 20G15, 14L24, 20E42     

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.     

On Trees with Double Domination Number Equal to the 2-Outer-Independent Domination Number Plus One

A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.     

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.     

Finite Groups Whose Minimal Subgroups are c-Supplemented

Let G be a finite group. A subgroup H of a group G is said to be c-supplemented in G if there exists a subgroup K of G such that G = HK and H ∩ K ≤ H _G , where H _G  = Core _G (H) is the largest normal subgroup of G contained in H. In this article, we investigate the structure of a finite group G under the assumption that subgroups of prime order are c-supplemented in G. Moreover, we analyze the structure of a group G when the minimal subgroups of the generalized Fitting subgroup F?(G) of G are c-supplemented in G through the theory of formations.     

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.     

An upper bound on the size of a largest clique in a graph

A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point-determining graph is the set G^O of all vertices, v, such that G–v is point determining. In this paper we show that the size, ω(G), of a maximum clique in G satisfies ω(G) ? 2|π (G)^O|, where π(G) (the point determinant of G) is obtained from G by identifying vertices which have the same neighborhood.     

Nearly m-embedded subgroups and solvability of finite groups

A subgroup A of a finite group G is called {1≤G}-embedded in G if for each two subgroups K≤H of G, where K is a maximal subgroup of H, A either covers the pair (K,H) or avoids it. Moreover, a subgroup H of G is called nearly m-embedded in G if G has a subgroup T and a {1≤G}-embedded subgroup C such that G?=?HT and H∩T≤C≤H. In this paper, we mainly prove that G is solvable if and only if its Sylow 3-subgroups, Sylow 5-subgroups and Sylow 7-subgroups are nearly m-embedded in G.     

A Note on c-Supplemented Subgroups of Finite Groups

A subgroup H of a finite group G is said to be c-supplemented in G if there exists a subgroup K of G such that G = HK and H ∩ K is contained in H _G , where H _G is the largest normal subgroup of G contained in H. In this article, we prove that G is solvable if every subgroup of prime odd order of G is c-supplemented in G. Moreover, we prove that G is solvable if and only if every Sylow subgroup of odd order of G is c-supplemented in G. These results improve and extend the classical results of Hall's articles of (1937) and the recent results of Ballester-Bolinches and Guo's article of (1999), Ballester-Bolinches et al.'s article of (2000), and Asaad and Ramadan's article of (2008).     

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     

On Weakly ℋ-embedded Subgroups of Finite Groups

Let G be a finite group and H a subgroup of G. We say that H is an ?-subgroup in G if N_G(H) ∩ H^g ≤ H for all g ∈ G; H is called weakly ?-subgroup in G if G has a normal subgroup K such that G = HK and H ∩ K is an ?-subgroup in G. We say that H is weakly ? -embedded in G if G has a normal subgroup K such that H^G = HK and H ∩ K is an ?-subgroup in G. In this paper, we investigate the structure of the finite group G under the assumption that some subgroups of prime power order are weakly ?-embedded in G. Our results improve and generalize several recent results in the literature.     

On properties of <Emphasis Type="Italic">G</Emphasis>-expansive homeomorphisms

We show that LUB of the set of G-expansive constants for a G-expansive homeomorphism h on a compact metric G-space, G compact, is not a G-expansive constant for h. We obtain a result regarding projecting and lifting of G-expansive homeomorphisms having interesting applications. We also prove that the G-expansiveness is a dynamical property for homeomorphisms on compact metric G-spaces and study G-periodic points.     

Maximal covers of finite groups

Abstract

Let λ(G) be the maximum number of subgroups in an irredundant covering of the finite group G. We prove that if G is a group with λ(G) ≤ 6, then G is supersolvable. We also describe the structure of groups G with λ(G) = 6. Moreover, we show that if G is a group with λ(G)?<?31, then G is solvable.