Classification of finite groups according to the number of conjugacy classes II

In the following,G denotes a finite group,r(G) the number of conjugacy classes ofG, β(G) the number of minimal normal subgroups ofG andα(G) the number of conjugate classes ofG not contained in the socleS(G). Let Φ _j = {G|β(G) =r(G) −j}. In this paper, the family Φ₁₁ is classified. In addition, from a simple inspection of the groups withr(G) =b conjugate classes that appear in ϒ _j ^=1/11 Φ _j , we obtain all finite groups satisfying one of the following conditions: (1)r(G) = 12; (2)r(G) = 13 andβ(G) > 1; …; (9)r(G) = 20 andβ(G) > 8; (10)r(G) =n andβ(G) =n −a with 1 ≦a ≦ 11, for each integern ≧ 21. Also, we obtain all finite groupsG with 13 ≦r(G) ≦ 20,β(G) ≦r(G) − 12, and satisfying one of the following conditions: (i) 0 ≦α(G) ≦ 4; (ii) 5 ≦α(G) ≦ 10 andS(G) solvable.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

Bounds on the Total Restrained Domination Number of a Graph

Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ _tr (G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ _tr (G) ≤ n − diam(G) − r + 1.     

On the Chromatic Number of H-Free Graphs of Large Minimum Degree

The problem of determining the chromatic number of H-free graphs has been well studied, with particular attention to K _r -free graphs with large minimum degree. Recent progress has been made for triangle-free graphs on n vertices with minimum degree larger than n/3. In this paper, we determine the family of r-colorable graphs H_r{\mathcal{H}_r}, such that if H ? H_r{H \in \mathcal{H}_r}, there exists a constant C < (r − 2)/(r − 1) such that any H-free graph G on n vertices with δ(G) > Cn has chromatic number bounded above by a function dependent only on H and C. A value of C < (r − 2)/(r − 1) is given for every H ? H_r{H \in \mathcal{H}_r}, with particular attention to the case when χ(H) = 3.     

On the average crosscap number II: Bounds for a graph

The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less thanβ(G)-1/2β(G)-1β(G) and not larger thanβ(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

Large holes in sparse random graphs

We show that there is a function α(r) such that for each constantr≧3, almost everyr-regular graph onn vertices has a hole (vertex induced cycle) of size at least α(r)n asn→∞. We also show that there is a function β(c) such that forc>0 large enough,G _{n, p} ,p=c/n almost surely has a hole of size at least β(c)n asn→∞.     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

If G is a connected graph of order n ⩾ 1, then by a hamiltonian coloring of G we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ⩾ n − 1 − D _G (x, y) (where D _G (x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

On the total domination subdivision numbers in graphs

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sd_{γ t} (G) ≤ 2γ _t (G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sd_{γ t} (G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sd_{γ t} (G)=2γ _t (G)−1.     

Relative Length of Longest Paths and Cycles in Graphs

For a graph G, let diff(G) = p(G) − c(G), where p(G) and c(G) denote the orders of a longest path and a longest cycle in G, respectively. Let G be a 3-connected graph of order n. In the paper, we give a best-possible lower bound to σ₄(G) to assure diff(G) ≤ 1. The result settles a conjecture in J. Graph Theory 37 (2001), 137–156.     

New Lower Bounds on the Multicolor Ramsey Numbers R r (C 2 m )

The multicolor Ramsey number R_r(H) is defined to be the smallest integer n=n(r) with the property that any r-coloring of the edges of the complete graph K_n must result in a monochromatic subgraph of K_n isomorphic to H. It is well known that 2^rm<R_r(C_2m+1)<2(r+2)!m and R_r(C_2m)≥(r−1)(m−1)+1. In this paper, we prove that R_r(C_2m)≥2(r−1)(m−1)+2. This research is supported by NSFC(60373096, 60573022) and SRFDP(20030141003)     

The Clique Numbers of Regular Graphs

 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:

Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d _G (u) + d _G (v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d _G (u) + d _G (v) ⩾ n − 2g + 3 (resp. d _G (u) + d _G (v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight. This work was supported by National Natural Science Foundation of China (Grant No. 10571013)     

New upper bounds for the Davenport and for the Erdős–Ginzburg–Ziv constants

Let G be a finite abelian group (written additively) of rank r with invariants n ₁, n ₂, . . . , n _r , where n _r is the exponent of G. In this paper, we prove an upper bound for the Davenport constant D(G) of G as follows; D(G) ≤ n _r + n _r-1 + (c(3) − 1)n _r-2 + (c(4) − 1) n _r-3 + · · · + (c(r) − 1)n ₁ + 1, where c(i) is the Alon–Dubiner constant, which depends only on the rank of the group \mathbb Z_nrⁱ{{\mathbb Z}_{n_r}^i}. Also, we shall give an application of Davenport’s constant to smooth numbers related to the Quadratic sieve.     

Some subgroups of semilinearly ordered groups

Let G be a semilinearly ordered group with a positive cone P. Denote byn(G) the greatest convex directed normal subgroup of G, byo(G) the greatest convex right-ordered subgroup of G, and byr(G) a set of all elements x of G such that x and x⁻¹ are comparable with any element of P^± (the collection of all group elements comparable with an identity element). Previously. it was proved thatr(G) is a convex right-ordered subgroup of G. andn(G) ⊆r(G) ⊆o(G). Here, we establish a new property ofr(G). and show that the inequalities in the given system of inclusions are, generally, strict. Supported by RFFR grant No. 99-01-00156. Translated fromAlgebra i Logika, Vol. 39, No. 4, pp. 465–479, July–August, 2000.