Complete Multipartite Graphs and the Relaxed Coloring Game

Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted ?? _g ^d (G). It is known that there exist graphs such that ?? _g ⁰(G)?=?3, but ?? _g ¹(G)?>?3. We will show that for all positive integers m, there exists a complete multipartite graph G such that m?????? _g ⁰(G)?<??? _g ¹(G).     

A new result on Davenport constant

Let G be a finite abelian group of order n and Davenport constant D(G). Let S=⁰h(S)_∏g∈Ggvg(S)∈F(G) be a sequence with a maximal multiplicity h(S) attained by 0 and t=|S|?n+D(G)−1. Then 0∈k_∑(S) for every 1?k?t+1−D(G). This is a refinement of the fundamental result of Gao [W.D. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996) 100-103].     

Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers

Let G be a graph of nonnegative characteristic and let g(G) and Δ(G) be its girth and maximum degree, respectively. We show that G has an edge-partition into a forest and a subgraph H so that (1) Δ(H)?1 if g(G)?11; (2) Δ(H)?2 if g(G)?7; (3) Δ(H)?4 if either g(G)?5 or G does not contain 4-cycles and 5-cycles; (4) Δ(H)?6 if G does not contain 4-cycles. These results are applied to find the following upper bounds for the game coloring number col_g(G) of G: (1) col_g(G)?5 if g(G)?11; (2) col_g(G)?6 if g(G)?7; (3) col_g(G)?8 if either g(G)?5 or G contains no 4-cycles and 5-cycles; (4) col_g(G)?10 if G does not contain 4-cycles.     

Characteristic polynomials of a permutation representation

Let G be a finite group. To each permutation representation (G, X) of G and class function χ of G we associate the χ-characteristic polynomialg_χ(x) of (G, X) which is a polynomial in one variable with complex numbers as coefficients. The coefficients of g_χ(x) are investigated in terms of the “exterior powers” of (G, X). If χ is the principal character 1_G of G, the coefficients of g_χ(x) are non-negative integers; and if furthermore G has odd order, the kth coefficient is the number of orbits of G acting on the subsets of X with k elements. Quadratic and linear relations among the exterior powers of (G, X) have been derived and it is shown how the polynomial g_χ(x) can be computed from the cycle index of (G, X).     

On the geodetic number of permutation graphs

A vertex set S in a graph G is a geodetic set if every vertex of G lies on some u?v geodesic of G, where u,v∈S. The geodetic number g(G) of G is the minimum cardinality over all geodetic sets of G. Let G ₁ and G ₂ be disjoint copies of a graph G, and let σ:V(G ₁)→V(G ₂) be a bijection. Then, a permutation graph G _σ =(V,E) has the vertex set V=V(G ₁)∪V(G ₂) and the edge set E=E(G ₁)∪E(G ₂)∪{uv∣v=σ(u)}. For any connected graph G of order n≥3, we prove the sharp bounds 2≤g(G _σ )≤2n?(1+△(G)), where △(G) denotes the maximum degree of G. We give examples showing that neither is there a function h ₁ such that g(G)<h ₁(g(G _σ )) for all pairs (G,σ), nor is there a function h ₂ such that h ₂(g(G))>g(G _σ ) for all pairs (G,σ). Further, we characterize permutation graphs G _σ satisfying g(G _σ )=2|V(G)|?(1+△(G)) when G is a cycle, a tree, or a complete k-partite graph.     

Minimal zero sum sequences of length four over finite cyclic groups

Text

Let G be a finite cyclic group. Every sequence S over G can be written in the form S=(n₁g)⋅…⋅(nlg) where g∈G and n₁,…,nl∈[1,ord(g)], and the index ind(S) of S is defined to be the minimum of (n₁+?+nl)/ord(g) over all possible g∈G such that 〈g〉=〈supp(S)〉. The problem regarding the index of sequences has been studied in a series of papers, and a main focus is to determine sequences of index 1. In the present paper, we show that if G is a cyclic of prime power order such that gcd(|G|,6)=1, then every minimal zero-sum sequence of length 4 has index 1.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=BC7josX_xVs.     

EDGE SUBDIVISIONS OF A GIVEN GEODETIC BLOCK PRESERVING ITS PROPERTY TO BE GEODETIC

1IntroductionInthispaperweshallconsideronlyundirected2-connectedsimplegraphs,i.e,graphsthatareloopless,finite,undirectedandwithoutmultipleedges.AgraphGissaidtobegeodeticifanypairofpointsofGarejoinedbyauniquepathofshortestlength,i.e,aulliquedistancepath[1].A2-connectedgeodeticgraphiscalledageodeticblock.Agrapllisgeodeticiffeachofitsblocksisgeodetic(seeStempleandWatkins['l).Obviously,oddcycle,tree,completegrapharegeodeticgraph,wecallthemthetrivialgeodeticgraph.Nowweonlycollsidertilenontrivial…     

Lower bounds for the game colouring number of partial k-trees and planar graphs

This paper discusses the game colouring number of partial k-trees and planar graphs. Let col_g(PT_k) and col_g(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this paper, we prove that col_g(PT_k)=3k+2 and col_g(P)?11. We also prove that the game colouring number col_g(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then col_g(H)?col_g(G).     

A description of Baer-Suzuki type of the solvable radical of a finite group

We obtain the following characterization of the solvable radical R(G) of any finite group G: R(G) coincides with the collection of all g∈G such that for any 3 elements a₁,a₂,a₃∈G the subgroup generated by the elements , i=1,2,3, is solvable. In particular, this means that a finite group G is solvable if and only if in each conjugacy class of G every 4 elements generate a solvable subgroup. The latter result also follows from a theorem of P. Flavell on {2,3}^′-elements in the solvable radical of a finite group (which does not use the classification of finite simple groups).     

On Finite n-Acentralizer Groups

Let G be a group and Aut(G) be the group of automorphisms of G. Then the Acentralizer of an automorphism α ∈Aut(G) in G is defined as C _G (α) = {g ∈ G∣α(g) = g}. For a finite group G, let Acent(G) = {C _G (α)∣α ∈Aut(G)}. Then for any natural number n, we say that G is n-Acentralizer group if |Acent(G)| =n. We show that for any natural number n, there exists a finite n-Acentralizer group and determine the structure of finite n-Acentralizer groups for n ≤ 5.     

Planar kernel and grundy with d≤3, dout≤2, din≤2 are NP-complete

It is proved that the questions whether a finite diagraph G has a kernel K or a Sprague—Grundy function g are NP-complete even if G is a cyclic planar digraph with degree constraints d_out(u)≤2, d_in(u)≤2 and d(u)≤3. These results are best possible (if P ≠ NP) in the sense that if any of the constraints is tightened, there are polynomial algorithms which either compute K and g or show that they do not exist. The proof uses a single reduction from planar 3-satisfiability for both problems.     

A matrix of combinatorial numbers related to the symmetric groups

For permutation groups G of finite degree we define numbers t_B(G)=|G|^-1∑_R∈G∏₁(1a₁(g))^b_i, where B=(b₁,…,b₁) is a tuple of non-negative integers and a₁(g) denotes the number of i cycles in the element g. We show that t_B(G) is the number of orbits of G, acting on a set Δ_B(G) of tuples of matrices. In the case G=S_n we get a natural interpretation for combinatorial numbers connected with the Stiring numbers of the second kind.     

The game of arboricity

Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by A_g(G). We prove that A_g(G)?3k for any graph G of arboricity k, and that there are graphs such that A_g(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.     

The hull and geodetic numbers of orientations of graphs

For an oriented graph D, let I_D[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let I_D[S] denote the union of all I_D[u,v] for all u,v∈S. Let [S]_D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_D[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]_D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g⁻(G)=min{g(D):D∈O(G)}, g⁺(G)=max{g(D):D∈O(G)}, h⁻(G)=min{h(D):D∈O(G)}, and h⁺(G)=max{h(D):D∈O(G)}. By the above definitions, h⁻(G)≤g⁻(G) and h⁺(G)≤g⁺(G). In the paper, we prove that g⁻(G)<h⁺(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g⁻(G)−h⁻(G)=a and g⁺(G)−h⁺(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].     

Optimally small sumsets in finite abelian groups

Let G be a finite abelian group of order g. We determine, for all 1?r,s?g, the minimal size μ_G(r,s)=min|A+B| of sumsets A+B, where A and B range over all subsets of G of cardinality r and s, respectively. We do so by explicit construction. Our formula for μ_G(r,s) shows that this function only depends on the cardinality of G, not on its specific group structure. Earlier results on μ_G are recalled in the Introduction.     

Injective coloring of planar graphs

A coloring of a graph G is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic numberχ_i(G) of a graph G is the least k such that there is an injective k-coloring. In this paper we prove that if G is a planar graph with girth g and maximum degree Δ, then (1) χ_i(G)=Δ if either g≥20 and Δ≥3, or g≥7 and Δ≥71; (2) χ_i(G)≤Δ+1 if g≥11; (3) χ_i(G)≤Δ+2 if g≥8.     

On equality of central and class preserving automorphisms of finite p-groups

Let G be a finite non-abelian p-group, where p is a prime. Let Aut_c(G) and Aut_z(G) respectively denote the group of all class preserving and central automorphisms of G. We give a necessary and sufficient condition for G such that Aut_c(G) = Aut_z(G) and classify all finite non-abelian p-groups G with elementary abelian or cyclic center such that Aut_c(G) = Aut_z(G). We also characterize all finite p-groups G of order ≤ p ⁷ such that Aut_z(G) = Aut_z(G) and complete the classification of all finite p-groups of order ≤ p ⁵ for which there exist non-inner class preserving automorphisms.     

A normal criterion about two families of meromorphic functions concerning shared values

In this paper, we mainly discuss the normality of two families of functions concerning shared values and proved: Let F and G be two families of functions meromorphic on a domain D■C,a1, a2, a3, a4 be four distinct finite complex numbers. If G is normal, and for every f ∈ F , there exists g ∈ G such that f(z) and g(z) share the values a1, a2, a3, a4, then F is normal on D.     

Engel-type subgroups and length parameters of finite groups

Let g be an element of a finite group G. For a positive integer n, let E _n (g) be the subgroup generated by all commutators [...[[x, g], g],..., g] over x ∈ G, where g is repeated n times. By Baer’s theorem, if E _n (g) = 1, then g belongs to the Fitting subgroup F(G). We generalize this theorem in terms of certain length parameters of E _n (g). For soluble G we prove that if, for some n, the Fitting height of E _n (g) is equal to k, then g belongs to the (k+1)th Fitting subgroup F_k+1(G). For nonsoluble G the results are in terms of nonsoluble length and generalized Fitting height. The generalized Fitting height h*(H) of a finite group H is the least number h such that F_h* (H) = H, where F₀* (H) = 1, and F_i+1(H)* is the inverse image of the generalized Fitting subgroup F*(H/F*_i (H)). Let m be the number of prime factors of |g| counting multiplicities. It is proved that if, for some n, the generalized Fitting height of E _n (g) is equal to k, then g belongs to F*_f(k,m)(G), where f(k, m) depends only on k and m. The nonsoluble length λ(H) of a finite group H is defined as the minimum number of nonsoluble factors in a normal series each of whose factors either is soluble or is a direct product of nonabelian simple groups. It is proved that if λ(E _n (g)) = k, then g belongs to a normal subgroup whose nonsoluble length is bounded in terms of k and m. We also state conjectures of stronger results independent of m and show that these conjectures reduce to a certain question about automorphisms of direct products of finite simple groups.