Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

A class of symmetric graphs with 2‐arc transitive quotients

Let Γ be an X‐symmetric graph admitting an X‐invariant partition ?? on V(Γ) such that Γ_?? is connected and (X, 2)‐arc transitive. A characterization of (Γ, X, ??) was given in [S. Zhou Eur J Comb 23 (2002), 741–760] for the case where |B|>|Γ(C)∩B|=2 for an arc (B, C) of Γ_??.We con‐sider in this article the case where |B|>|Γ(C)∩B|=3, and prove that Γ can be constructed from a 2‐arc transitive graph of valency 4 or 7 unless its connected components are isomorphic to 3 K ₂, C ₆ or K _{3, 3}. As a byproduct, we prove that each connected tetravalent (X, 2)‐transitive graph is either the complete graph K ₅ or a near n‐gonal graph for some n?4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 232–245, 2010     

Representing abstract groups by powers of a graph

We deal with the problem of representing several abstract groups simultaneously by one graph as automorphism groups of its powers. We call subgroups Γ₁,…, Γ_n of a finite group Γ representable iff there is a graph G and an injective mapping φ from ∪_i=1ⁿΓ_i into the symmetric group on V(G) such that for i=1,…, n φ|_Γi is a monomorphism onto Aut Gⁱ. We give a necessary and a sufficient condition for groups being representable, the latter implying, e.g., that finite groups Γ₁≤…≤Γ_n are representable.     

On the diameters of commuting graphs

The commuting graph of a ring R, denoted by Γ(R), is a graph whose vertices are all non-central elements of R and two distinct vertices x and y are adjacent if and only if xy = yx. Let D be a division ring and n ? 3. In this paper we investigate the diameters of Γ(M_n(D)) and determine the diameters of some induced subgraphs of Γ(M_n(D)), such as the induced subgraphs on the set of all non-scalar non-invertible, nilpotent, idempotent, and involution matrices in M_n(D). For every field F, it is shown that if Γ(M_n(F)) is a connected graph, then diam Γ(M_n(F)) ? 6. We conjecture that if Γ(M_n(F)) is a connected graph, then diam Γ(M_n(F)) ? 5. We show that if F is an algebraically closed field or n is a prime number and Γ(M_n(F)) is a connected graph, then diam Γ(M_n(F)) = 4. Finally, we present some applications to the structure of pairs of idempotents which may prove of independent interest.     

A constructive description of Hölder classes on closed Jordan curves

Let Γ be a closed, Jordan, rectifiable curve, whose are length is commensurable with its subtending chord, leta ε int Γ, and let R_n(a) be the set of rational functions of degree ≤n, having a pole perhaps only at the pointa. Let Λ^α(Γ), 0 < α < 1, be the Hölder class on Γ. One constructs a system of weights γ_n(z) > 0 on Γ such that f∈Λ^α(Γ) if and only if for any nonnegative integer n there exists a function R_n, R_n ε R_n(a) such that ¦f(z) ? R_n(z)¦ ≤ c_f·γ_n(z), z ε Γ. It is proved that the weights γ_n cannot be expressed simply in terms of ρ ₁ ⁺ /n^(z) and ρ ₁ ^- /n^(z), the distances to the level lines of the moduli of the conformal mappings of ext Γ and int Γ on \(\mathbb{C}\backslash \mathbb{D}\) .     

Group action for enumerating maps on surfaces

A map is a connected topological graph Γ cellularly embedded in a surface. For any connected graph Γ, by introducing the conception of semi-arc automorphism groupAut1/2 Γ and classifying all embedding of Γ under the action of this group, the numbersr ^o (Γ) andr ^N (Γ) of rooted maps on orientable and non-orientable surfaces with underlying graph Γ are found. Many closed formulas without sum Σ for the number of rooted maps on surfaces (orientable or non-orientable) with given underlying graphs, such as, complete graphK _n , complete bipartite graphK _m,n, bouquetsB _n , dipoleDp _n and generalized dipoleDp _n ^k,l are refound in this paper.     

On the generating graph of direct powers of a simple group

Let S be a nonabelian finite simple group and let n be an integer such that the direct product S ⁿ is 2-generated. Let Γ(S ⁿ ) be the generating graph of S ⁿ and let Γ _n (S) be the graph obtained from Γ(S ⁿ ) by removing all isolated vertices. A recent result of Crestani and Lucchini states that Γ _n (S) is connected, and in this note we investigate its diameter. A deep theorem of Breuer, Guralnick and Kantor implies that diam(Γ ₁(S))=2, and we define Δ(S) to be the maximal n such that diam(Γ _n (S))=2. We prove that Δ(S)≥2 for all S, which is best possible since Δ(A ₅)=2, and we show that Δ(S) tends to infinity as |S| tends to infinity. Explicit upper and lower bounds are established for direct powers of alternating groups.     

The number of Hamiltonian decompositions of regular graphs

A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph K _n on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r = cn for some fixed c > 1/2 has a Hamiltonian decomposition, provided n = n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ) = r ^(1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of K _n is \({n^{\left( {1 + o\left( 1 \right)} \right){n^2}/2}}\).     

Two applications of semi-stable graphs

A Michigan graph G on a vertex set V is called semi-stable if for some υ?V, Γ(G_υ) = Γ(G)_υ. It can be shown that all regular graphs are semi-stable and this fact is used to show (i) that if Γ(G) is doubly transitive then G = K_n or K?_n, and (ii) that Γ(G) can be recovered from Γ(G_υ). The second result is extended to the case of stable graphs.     

Codes from incidence matrices of graphs

We examine the p-ary codes, for any prime p, from the row span over ${\mathbb {F}_p}$ of |V| × |E| incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| ? 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k ? 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.     

Edge-bipancyclicity of a hypercube with faulty vertices and edges

A bipartite graph G=(V,E) is said to be bipancyclic if it contains a cycle of every even length from 4 to |V|. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F_v (respectively, F_e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_n. In this paper, we show that every edge of Q_n-F_v-F_e lies on a cycle of every even length from 4 to 2ⁿ-2|F_v| even if |F_v|+|F_e|?n-2, where n?3. Since Q_n is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.     

Bounding the diameter of a distance-transitive graph

A graph Γ is distance-transitive if for all vertices u, v, x, y such that d(u, v) = d(x, y) there is an automorphism h of Γ such that uh = x, vh = y. We show how to find a bound for the diameter of a bipartite distance-transitive graph given a bound for the order |G_α| of the stabilizer of a vertex.     

Distance-transitive representations of the symmetric groups

Let Γ be a graph and G ≤ Aut(Γ). The group G is said to act distance-transitively on Γ if, for any vertices x, y, u, v such that ∂(x, y) = ∂(u, v), there is an element g ϵ G mapping x into u and y into v. If G acts distance-transitively on Γ then the permutation group induced by the action of G on the vertex set of Γ is called the distance-transitive representation of G. In the paper all distance-transitive representations of the symmetric groups S_n are classified. Moreover, all pairs (G, Γ) such that G acts distance-transitively on Γ and G = S_n for some n are described. The classification problem for these pairs was posed by N. Biggs (Ann. N.Y. Acad. Sci. 319 (1979), 71–81). The problem is closely related to the general question about distance-transitive graphs with given automorphism group.     

Invariant random subgroups of linear groups

Let Γ < GL _n (_F) be a countable non-amenable linear group with a simple, center free Zariski closure. Let Sub(Γ) denote the space of all subgroups of Γ with the compact, metric, Chabauty topology. An invariant random subgroup (IRS) of Γ is a conjugation invariant Borel probability measure on Sub(Γ). An IRS is called non-trivial if it does not have an atom in the trivial group, i.e. if it is non-trivial almost surely. We denote by IRS⁰(Γ) the collection of all non-trivial IRS on Γ.

Theorem 0.1: With the above notation, there exists a free subgroup F < Γ and a non-discrete group topology on Γ such that for every μ ∈ IRS⁰(Γ) the following properties hold:

μ-almost every subgroup of Γ is open

• F ·Δ = Γ for μ-almost every Δ ∈ Sub(Γ).
• F ∩ Δ is infinitely generated, for every open subgroup. In particular, this holds for μ-almost every Δ ∈ Sub(Γ).
• The map

Φ: (Sub(Γ), μ) → (Sub(F),Φ*μ) Δ → Δ ∩ F is an F-invariant isomorphism of probability spaces.A more technical version of this theorem is valid for general countable linear groups. We say that an action of Γ on a probability space, by measure preserving transformations, is almost surely non-free (ASNF) if almost all point stabilizers are non-trivial.Corollary 0.2: Let Γ be as in the Theorem above. Then the product of finitely many ASNF Γ-spaces, with the diagonal Γ action, is ASNF.Corollary 0.3: Let Γ < GL_n(F) be a countable linear group, A Δ Γ the maximal normal amenable subgroup of Γ — its amenable radical. If μ ∈ IRS(Γ) is supported on amenable subgroups of Γ, then in fact it is supported on Sub(A). In particular, if A(Γ) = <e> then Δ = <e>, μ almost surely.     

On a question of Külshammer for representations of finite groups in reductive groups

Let G be a simple algebraic group of type G₂ over an algebraically closed field of characteristic 2. We give an example of a finite group Γ with Sylow 2-subgroup Γ₂ and an infinite family of pairwise non-conjugate homomorphisms ρ: Γ → G whose restrictions to Γ₂ are all conjugate. This answers a question of Burkhard Külshammer from 1995. We also give an action of Γ on a connected unipotent group V such that the map of 1-cohomologies H¹(Γ, V) → H¹(Γ_p, V) induced by restriction of 1-cocycles has an infinite fibre.     

Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity

Let Γ be a connected simple graph, let V(Γ) and E(Γ) denote the vertex-set and the edge-set of Γ, respectively, and let n=|V(Γ)|. For 1≤i≤n, let e_i be the element of elementary abelian group which has 1 in the ith coordinate, and 0 in all other coordinates. Assume that V(Γ)={e_i∣1≤i≤n}. We define a set Ω by Ω={e_i+e_j∣{e_i,e_j}∈E(Γ)}, and let Cay_Γ denote the Cayley graph over with respect to Ω. It turns out that Cay_Γ contains Γ as an isometric subgraph. In this paper, the relations between the spectra of Γ and Cay_Γ are discussed. Some conditions on the existence of Hamilton paths and cycles in Γ are obtained.     

F-Sets in graphs

A subset S of the vertex set of a graph G is called an F-set if every α?Γ(G), the automorphism group of G, is completely specified by specifying the images under α of all the points of S, and S has a minimum number of points. The number of points, k(G), in an F-set is an invariant of G, whose properties are studied in this paper. For a finite group Γ we define k(Γ) = max{k(G) | Γ(G) = Γ}. Graphs with a given Abelian group and given k-value (k ≤ k(Γ)) have been constructed. Graphs with a given group and k-value 1 are constructed which give simple proofs to the theorems of Frucht and Bouwer on the existence of graphs with given abstract/permutation groups.     

A new estimate for the vertex number of an edge-regular graph

Given a connected edge-regular graph Γ with parameters (v, k, λ) and b ₁ = k ? λ ? 1, we prove that in the case k ≥ 3b ₁ ?2 either |Γ₂(u)|(k?2b ₁ + 2) < kb ₁ for every vertex u or Γ is a polygon, the edge graph of a trivalent graph without triangles that has diameter greater than 2, the icosahedral graph, the complete multipartite graph K _r×2, the 3 × 3-grid, the triangular graph T(m) with m ≤ 7, the Clebsch graph, or the Schläfli graph.     

On the Commuting Graph of Dihedral Group

Let Γ be a non-abelian group and Ω ? Γ. We define the commuting graph G = 𝒞(Γ, Ω) with vertex set Ω and two distinct elements of Ω are joined by an edge when they commute in Γ. In this article, among some properties of commuting graphs, we investigate distant properties as well as detour distant properties of commuting graph on D_2n. We also study the metric dimension of commuting graph on D_2n and compute its resolving polynomial.     

Homogeneoys graphs

Let Γ be a finite graph with vertex set VΓ, and let U, V be arbitrary subsets of VΓ. Γ is homogeneoys (resp. ultrahomogeneous) if whenever the induced subgraphs 〈U〉, 〈V〉 are isomorphic, some isomorphism (resp. every isomorphism) of 〈U〉 onto 〈V〉 extends to an automorphism of Γ. We extend a theorem of Sheehan on ultrahomogeneous graphs to the homogeneous case, and complete his classification of ultrahomogenous graphs.