On mutually permutable products of finite groups

We say that the subgroups G ₁ and G ₂ of a group G are mutually permutable if G ₁ permutes with every subgroup of G ₂ and G ₂ permutes with every subgroup of G ₁. Let G=G ₁ G ₂…G _n be the product of its pairwise permutable subgroups G ₁,G ₂,…,G _n such that the product G _i G _j is mutually permutable. We investigate the structure of the finite group G if special properties of the factors G ₁,G ₂,…,G _n are known. Our results improve and extend some results of Asaad and Shaalan [1], Ezquerro and Soler-Escrivà [9] and Asaad and Monakhov [3].     

Continuous dependence of attractors on the shape of domain

Let Ω₀ be a bounded domain in ? ⁿ , letG be a family of diffeomorphisms, and let Ω _G =G(Ω₀), forG∈G. Denote by Σ _t (G) the semigroup generated by a fixed parabolic PDE with Dirichlet boundary conditions on the boundary of Ω _G . LetA _G be the global attractor of Σ _t (G). Conditions are given under which a generic diffeomorphismG∈G is a continuity point of the mapG »A _G . Bibliography: 12 titles.     

Panconnectivity for interconnection networks with faulty elements

Let Go and G1 be two graphs with the same vertices. The new graph G（G0, G1; M） is a graph with the vertex set V（0o） ∪）V（G1） and the edge set E（Go） UE（G1） UM, where M is an arbitrary perfect matching between the vertices of Go and G1, i.e., a set of cross edges with one endvertex in Go and the other endvertex in G1. In this paper, we will show that if Go and G1 are f-fault q-panconnected, then for any f 〉 2, G（G0, G1; M） is （f ＋ 1）-fault （q ＋ 2）-panconnected.     

Hamiltonicity of 6-connected line graphs

Let G be a graph and let D₆(G)={v∈V(G)|d_G(v)=6}. In this paper we prove that: (i) If G is a 6-connected claw-free graph and if |D₆(G)|≤74 or G[D₆(G)] contains at most 8 vertex disjoint K₄’s, then G is Hamiltonian; (ii) If G is a 6-connected line graph and if |D₆(G)|≤54 or G[D₆(G)] contains at most 5 vertex disjoint K₄’s, then G is Hamilton-connected.     

Some sufficient conditions for a finite group to be supersolvable

This paper represents an attempt to extend and improve the following result of Berkovich: Let G be a group of odd order. Let G=G ₁ G ₂ such that G ₁ and G ₂ are subgroups of?G. If the Sylow p-subgroups of G ₁ and of G ₂ are cyclic, then G is p-supersolvable.     

On the Colin de Verdière numbers of Cartesian graph products

Let G be a connected graph with Colin de Verdière number μ(G). We study the behaviour of μ with respect to the Cartesian product of graphs. We conjecture that if G=G₁□G₂, with G₁,G₂ connected, then μ(G)?μ(G₁)+μ(G₂) and prove that μ(G)?μ(G₁)+h(G₂)-1, where h is the Hadwiger number (i.e. the order of the largest clique minor). In addition we provide an explicit construction of a Colin de Verdière matrix with corank μ(G₁)+μ(K_n) for the graph G=G₁□K_n.     

On groups factorizable in commuting almost locally normal subgroups

We prove that anRN-group (in particular, locally solvable)G =G ₁ G ₂ ...G _n withG _i and π(G _i ) ∩ π(G _j ) = ?,i ≠j is a periodic hyper-Abelian group if the subgroupsG _j are almost locally normal.     

The Ramsey number for a cycle of length six versus a clique of order eight

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let C_m denote a cycle of length m and K_n a complete graph of order n. In this paper, it is shown that R(C₆,K₈)=36.     

A Counter-Example to Martino’s Conjecture About Generic Calogero–Moser Families

The Calogero–Moser families are partitions of the irreducible characters of a complex reflection group derived from the block structure of the corresponding restricted rational Cherednik algebra. It was conjectured by Martino in 2009 that the generic Calogero–Moser families coincide with the generic Rouquier families, which are derived from the corresponding Hecke algebra. This conjecture is already proven for the whole infinite series G(m,p,n) and for the exceptional group G ₄. A combination of theoretical facts with explicit computations enables us to determine the generic Calogero–Moser families for the nine exceptional groups G ₄, G ₅, G ₆, G ₈, G ₁₀, G ₂₃?=?H ₃, G ₂₄, G ₂₅, and G ₂₆. We show that the conjecture holds for all these groups—except surprisingly for the group G ₂₅, thus being the first and only-known counter-example so far.     

Kirchhoff index of composite graphs

Let G₁+G₂, G₁°G₂ and G₁{G₂} be the join, corona and cluster of graphs G₁ and G₂, respectively. In this paper, Kirchhoff index formulae of these composite graphs are given.     

The basis monomial ring of a matroid

We define the basis monomial ring M_G of a matroid G and prove that it is Cohen-Macaulay for finite G. We then compute the Krull dimension of M_G, which is the rank over Q of the basis-point incidence matrix of G, and prove that dim B_G ≥ dim M_G under a certain hypothesis on coordinatizability of G, where B_G is the bracket ring of G.     

On the edge-connectivity and restricted edge-connectivity of a product of graphs

The product graph G_m*G_p of two given graphs G_m and G_p was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32-48]. For this kind of graphs we provide bounds for two connectivity parameters (λ and λ^′, edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs G_m, G_p of minimum degrees δ(G_m), δ(G_p), respectively, we show that λ(G_m*G_p) is lower bounded by both δ(G_m)+λ(G_p) and δ(G_p)+λ(G_m), an improvement of what is known for the edge-connectivity of G_m×G_p.     

On the Sylow graph of a group and Sylow normalizers

Let G be a finite group and G _p be a Sylow p-subgroup of G for a prime p in π(G), the set of all prime divisors of the order of G. The automiser A _p (G) is defined to be the group N _G (G _p )/G _p C _G (G _p ). We define the Sylow graph Γ _A (G) of the group G, with set of vertices π(G), as follows: Two vertices p, q ∈ π(G) form an edge of Γ _A (G) if either q ∈ π(A _p (G)) or p ∈ π(A _q (G)). The following result is obtained Theorem: Let G be a finite almost simple group. Then the graph Γ _A (G) is connected and has diameter at most 5. We also show how this result can be applied to derive information on the structure of a group from the normalizers of its Sylow subgroups.     

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.     

The genus of the Cartesian product of two graphs

Upper and lower bounds are given for the genus, γ(G₁ × G₂), of the Cartesian product of arbitrary graphs G₁ and G₂, in terms of the genera γ(G₁) and γ(G₂). These bounds are then used to obtain asymptotic results for the cases in which G₁ and G₂ are both regular complete k-partite graphs.     

Graphs determined by their generalized characteristic polynomials

For a given graph G with (0, 1)-adjacency matrix A_G, the generalized characteristic polynomial of G is defined to be ?_G=?_G(λ,t)=det(λI-(A_G-tD_G)), where I is the identity matrix and D_G is the diagonal degree matrix of G. In this paper, we are mainly concerned with the problem of characterizing a given graph G by its generalized characteristic polynomial ?_G. We show that graphs with the same generalized characteristic polynomials have the same degree sequence, based on which, a unified approach is proposed to show that some families of graphs are characterized by ?_G. We also provide a method for constructing graphs with the same generalized characteristic polynomial, by using GM-switching.     

Connectivity measures in matched sum graphs

A matched sum graph G of two graphs G₁ and G₂ of the same order is obtained from the union of G₁ and G₂ and from joining each vertex of G₁ with one vertex of G₂ according to one bijection f between the vertices in V(G₁) and V(G₂). When G₁=G₂=H then f is just a permutation of V(H) and the corresponding matched sum graph is a permutation graph H^f. In this paper, we derive lower bounds for the connectivity, edge-connectivity, and different conditional connectivities in matched sum graphs, and present sufficient conditions which guarantee maximum values for these conditional connectivities.     

Packings of graphs and applications to computational complexity

Let G₁ and G₂ be graphs with n vertices. If there are edge-disjoint copies of G₁ and G₁ with the same n vertices, then we say there is a packing of G₁ and G₂. This paper is concerned with establishing conditions on G₁ and G₂ under which there is a packing. Our main result (Theorem 1) shows that, with very few exceptions, if G₁ and G₂ together have at most 2n?3 edges and no vertex is joined to all other vertices, then there is a packing of G₁ and G₂. Our packing results have some applications to computational complexity. In particular, we show that, for subgraphs of tournaments, the property of containing a sink is a monotone property with minimal computational complexity.     

A note on Ramsey multiplicity

If G₁ and G₂ are graphs and the Ramsey number r(G₁, G₂) = p, then the fewest number of G₁ in G and G₂ in ? (G complement) that occur in a graph G on p points is called the Ramsey multiplicity and denoted R(G₁, G₂). In [2, 3] the diagonal (i.e. G₁ = G₂) Ramsey multiplicities are derived for graphs on 3 and 4 points, with the exception of K₄. In this note an upper bound is established for R(K_s, K₁). Specifically, we show that R(K₄, K₄) ? 12.