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.      

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.     

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 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     

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     

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 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.     

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.     

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 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.     

Characterizations of G-tube domains

Let G be a real connected Lie group for which the universal complexification G ^ℂ has a polar decomposition G ^ℂ≅G exp(i?), where ? denotes the Lie algebra of G. The present paper is concerned with Riemann G-domains over the complex group G ^ℂ viewed as a G-manifold via the left multiplication. Such a Riemann domain X is said to be of Reinhardt type if G contains a discrete cocompact subgroup $\Gamma$ for whichG/Γ is a Stein manifold. Here the following is proved: Every Riemann G-domain of Reinhardt type is schlicht, hence a G-tube domain, i.e., a G-invariant subdomain of G ^ℂ. As an application one obtains conditions for a holomorphically separable G-manifold to be a G-tube domain. Received: 22 October 1998     

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.     

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.     

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).     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008