Decomposition of bipartite graphs into special subgraphs

Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F₁,F₂,…,F_m is called an F-factorization of G orthogonal to H if F_i≅F and |E(F_i∩H)|=1 for each i=1,2,…,m. Gyárfás and Schelp conjectured that the complete bipartite graph K_4k,4k has a C₄-factorization orthogonal to H provided that H is a k-factor of K_4k,4k. In this paper, we show that (1) the conjecture is true when H satisfies some structural conditions; (2) for any two positive integers r?k, K_kr²,kr² has a K_r,r-factorization orthogonal to H if H is a k-factor of K_kr²,kr²; (3) K_2d²,2d² has a C₄-factorization such that each edge of H belongs to a different C₄ if H is a subgraph of K_2d²,2d² with maximum degree Δ(H)?d.     

Fitting Height of a Finite Group with a Metabelian Group of Automorphisms

Let M = FH be a finite group that is a product of a normal abelian subgroup F and an abelian subgroup H. Assume that all elements in M?F have prime order p, and F has at most one subgroup of order p. Examples of such groups are dihedral groups for p = 2 and the semidirect product of a cyclic group F by a group H of prime order p such that C _F (H) = 1 or |C _F (H)| =p and C _{F/C F (H)}(H) = 1. Suppose that M acts on a finite group G in such a manner that C _G (F) = 1. We prove that the Fitting height h(G) of G is at most h(C _G (H))+ 1. Moreover, the Fitting series of C _G (H) coincides with the intersection of C _G (H) with the Fitting series of G.     

Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.     

Modules over integer group rings of locally soluble groups with minimax restriction

Let ? be the ring of integers, and A be a ?G-module, where A/C _A (G) is not a minimax ?-module, C _G (A) = 1, and G is a locally soluble group. Let L _nm(G) be the system of all subgroups H ?? G such that quotient modules A/C _A (H) are not minimax Z-modules. The author studies ?G-modules A such that L _nm(G) satisfies the minimal condition as an ordered set. It is proved that a locally soluble group G with these conditions is soluble. The structure of the group G is described.     

A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Cocharacters of Bilinear Mappings and Graded Matrices

Let M _k (F) be the algebra of k ×k matrices over a field F of characteristic 0. If G is any group, we endow M _k (F) with the elementary grading induced by the k-tuple (1,...,1,g) where g?∈?G, g ²?≠?1. Then the graded identities of M _k (F) depending only on variables of homogeneous degree g and g ^???1 are obtained by a natural translation of the identities of bilinear mappings (see Bahturin and Drensky, Linear Algebra Appl 369:95–112, 2003). Here we study such identities by means of the representation theory of the symmetric group. We act with two copies of the symmetric group on a space of multilinear graded polynomials of homogeneous degree g and g ^???1 and we find an explicit decomposition of the corresponding graded cocharacter into irreducibles.     

More on the generalized Macaulay theorem

Let k₁ ? k₂ ? … ? k_n be given positive integers and let F denote the set of vectors (l₁, …, l_n) with integer components satisfying 0 ? l_i ? k_i, i = 1, 2, …, n. If H is a subset of F, let (l)H denote the subset of H consisting of those vectors with component sum l, and let C((l)H) denote the smallest [(l)H] elements of (l)F. The generalized Macaulay theorem due to the author and B. Lindström [3] shows that |Gamma;((C)(l)(H)|, ? |Γ(C((l)H))|, where Γ((l)H) is the setof vectors in F obtainable by subtracting l from a single component of a vector in (l)H. A method is given for computing [Γ(C((l)H)] in this paper. It is analogous to the method for computing |Γ(C(l)H))| in the k₁ = … = k_n = 1 case which has been given independently by Katona [4] and Kruskal [5].     

Primitive words,free factors and measure preservation

Let F _k be the free group on k generators. A word w ∈ F _k is called primitive if it belongs to some basis of F _k . We investigate two criteria for primitivity, and consider more generally subgroups of F _k which are free factors. The first criterion is graph-theoretic and uses Stallings core graphs: given subgroups of finite rank H ≤ J ≤ F _k we present a simple procedure to determine whether H is a free factor of J. This yields, in particular, a procedure to determine whether a given element in F _k is primitive. Again let w ∈ F _k and consider the word map w: G × … × G → G (from the direct product of k copies of G to G), where G is an arbitrary finite group. We call w measure preserving if given uniform measure on G × … × G, w induces uniform measure on G (for every finite G). This is the second criterion we investigate: it is not hard to see that primitivity implies measure preservation, and it was conjectured that the two properties are equivalent. Our combinatorial approach to primitivity allows us to make progress on this problem and, in particular, prove the conjecture for k = 2. It was asked whether the primitive elements of F _k form a closed set in the profinite topology of free groups. Our results provide a positive answer for F ₂.     

On the motivic class of the stack of bundles

Let G be a split connected semisimple group over a field. We give a conjectural formula for the motivic class of the stack of G-bundles over a curve C, in terms of special values of the motivic zeta function of C. The formula is true if C=P¹ or G=SLn. If k=C, upon applying the Poincaré or called the Serre characteristic by some authors the formula reduces to results of Teleman and Atiyah-Bott on the gauge group. If k=Fq, upon applying the counting measure, it reduces to the fact that the Tamagawa number of G over the function field of C is |π₁(G)|.     

Tension-flow polynomials on graphs

An orientation of a graph is acyclic (totally cyclic) if and only if it is a “positive orientation” of a nowhere-zero integral tension (flow). We unify the notions of tension and flow and introduce the so-called tension-flows so that every orientation of a graph is a positive orientation of a nowhere-zero integral tension-flow. Furthermore, we introduce an (integral) tension-flow polynomial, which generalizes the (integral) tension and (integral) flow polynomials. For every graph G, the tension-flow polynomial F_G(k₁,k₂) on G and the Tutte polynomial T_G(k₁,k₂) on G satisfy F_G(k₁,k₂)⩽T_G(k₁−1,k₂−1). We also characterize the graphs for which the inequality is sharp.     

A constructive characterization of trees with at least k disjoint maximum matchings

Let H = F(v) ⊕ G(w) denote the graph obtained from F and G by identifying vertices v of F and w of G; H will be said to be obtained by surgery on F and G. A matching of a graph is a collection of edges, no two of which are incident with the same vertex. This paper presents a constructive characterization of the set S_k (k ≥ 2) of trees which have at least k disjoint maximum matchings. There are three types of surgery such that, for each k ≥ 2, S_k is the set of all trees obtainable from a star K_1.n (n ≥ k) by a finite sequence of the specified surgical operations. A constructive characterization is also given for trees with two disjoint maximum indepent vertex sets.     

The connected Ramsey number

A graph G is totally connected if both G and ? (its complement) are connected. The connected Ramsey number r_c(F, H) is the smallest integer k ? 4 so that if G is a totally connected graph of order k then either F ? G or H ? ?. We show that if neither of F nor H contains a bridge, then r_c = r(F, H), the usual generalized Ramsey number of F and H. We compute r_c (P_mP_m), the connected Ramsey number for paths.     

Vertex Coverings by Coloured Induced Graphs—Frames and Umbrellas

A graph G homogeneously embeds in a graph H if for every vertex x of G and every vertex y of H there is an induced copy of G in H with x at y. The graph G uniformly embeds in H if for every vertex y of H there is an induced copy of G in H containing y. For positive integer k, let f_k(G) (respectively, g_k(G)) be the minimum order of a graph H whose edges can be k-coloured such that for each colour, G homogeneously embeds (respectively, uniformly embeds) in the graph given by V(H) and the edges of that colour. We investigate the values f₂(G) and g₂(G) for special classes of G, in particular when G is a star or balanced complete bipartite graph. Then we investigate f_k(G) and g_k(G) when k ≥ 3 and G is a complete graph.     

Power inequalities and spectral dominance of generalized matrix norms

A generalized matrix norm G dominates the spectral radius for all A?M_n(C) (i) if for some positive integer k the rule G(A^k) ? G(A)^k holds for all A?M_n(C) and (ii) if and only if for each A?M_n(C) there exists a constant γ_A such that G(A^k) ? γ_AG(A)^kfor all positive integers k. Other results and examples are also given concerning spectrally dominant generalized matrix norms.     

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

Upon the removal of the edges of a 1-factor from an even circuit in a 2-connected graph

Let G be a 2-connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G with factorization F={F₁,F₂} such that G−E(F₁) is 2-connected.     

Étude du cas rationnel de la théorie des formes linéaires de logarithmes

We establish new measures of linear independence of logarithms on commutative algebraic groups in the so-called rational case. More precisely, let k be a number field and v₀ be an arbitrary place of k. Let G be a commutative algebraic group defined over k and H be a connected algebraic subgroup of G. Denote by Lie(H) its Lie algebra at the origin. Let u∈Lie(G(Cv₀)) a logarithm of a point p∈G(k). Assuming (essentially) that p is not a torsion point modulo proper connected algebraic subgroups of G, we obtain lower bounds for the distance from u to Lie(H)k_⊗Cv₀. For the most part, they generalize the measures already known when G is a linear group. The main feature of these results is to provide a better dependence in the height loga of p, removing a polynomial term in logloga. The proof relies on sharp estimates of sizes of formal subschemes associated to H (in the sense of Bost) obtained from a lemma by Raynaud as well as an absolute Siegel lemma and, in the ultrametric case, a recent interpolation lemma by Roy.     

Graham’s pebbling conjecture on products of many cycles

A pebbling move on a connected graph G consists of removing two pebbles from some vertex and adding one pebble to an adjacent vertex. We define f_t(G) as the smallest number such that whenever f_t(G) pebbles are on G, we can move t pebbles to any specified, but arbitrary vertex. Graham conjectured that f₁(G×H)≤f₁(G)f₁(H) for any connected G and H. We define the α-pebbling number α(G) and prove that α(C_pj×?×C_p2×C_p1×G)≤α(C_pj)?α(C_p2)α(C_p1)α(G) when none of the cycles is C₅, and G satisfies one more criterion. We also apply this result with G=C₅×C₅ by showing that C₅×C₅ satisfies Chung’s two-pebbling property, and establishing bounds for f_t(C₅×C₅).