The power graph of a finite group

The power graph of a group is the graph whose vertex set is the group, two elements being adjacent if one is a power of the other. We observe that non-isomorphic finite groups may have isomorphic power graphs, but that finite abelian groups with isomorphic power graphs must be isomorphic. We conjecture that two finite groups with isomorphic power graphs have the same number of elements of each order. We also show that the only finite group whose automorphism group is the same as that of its power graph is the Klein group of order 4.     

On the graph for which there is a tree as the inverse interchange graph of a local graph

Let G be a finite, connected, undirected graph without loops and multiple edges. The note modifies slightly the concept of I^–1 (T_t), the inverse interchange graph of the local graph G(T_t) defined by a reference tree t G, and considers the properties of the graph G, when I^–1(T_t) is a tree.     

The homology of a locally finite graph with ends

We show that the topological cycle space of a locally finite graph is a canonical quotient of the first singular homology group of its Freudenthal compactification, and we characterize the graphs for which the two coincide. We construct a new singular-type homology for non-compact spaces with ends, which in dimension 1 captures precisely the topological cycle space of graphs but works in any dimension.     

Every finite graph is a full subgraph of a rigid graph

We prove that every finite undirected graph is a full subgraph of a rigid graph. Our construction proceeds on taking a family of “mutually rigid” graphs and attaching them to the vertices of a given graph in a one-to-one manner; then the vertices are fixed on their place. Actually, the new graph is “strongly rigid”, which enables us to show that the category of all graphs containing a given finite graph as a full subgraph is binding.     

The fundamental group of a locally finite graph with ends

We characterize the fundamental group of a locally finite graph G with ends combinatorially, as a group of infinite words. Our characterization gives rise to a canonical embedding of this group in the inverse limit of the free groups π₁(G^′) with G^′⊆G finite.     

The generating graph of finite soluble groups

For a finite group G, let Γ(G) denote the graph defined on the non-identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. We prove that if G is soluble, then the non-isolated vertices of Γ(G) belong to a unique connected component.     

The finiteness of the number of symmetrical extensions of a locally finite tree by a finite graph

The problem of incidence of an acoustic wave on the interface between media with impedance interface conditions is considered. An approximate method is proposed for calculating the result of diffraction under such conditions. The method is implemented as a computer program, and the result is compared with the analytical solution for the impedance conditions and with the calculations by a program for the contact boundary conditions. Good accuracy of the method and high computation speed are demonstrated, which allow one to apply the proposed approximate method to solving both direct and inverse problems of acoustics.     

The spectrum of the averaging operator for a finite homogeneous graph

We give an estimate for the spectrum of the averaging operator T₁(Γ, 1) over the radius 1 for the finite (q+1)-homogeneous quotient graph Γ/X, where X is an infinite (q+1)-homogeneous tree associated with the free group G over a finite set of generators S={x₁ ..., x_p} (2p=q+1), and Γ, a subgroup of finite index in G. T₁(Γ, 1) is defined on the subspace L²(Γ/G, 1) ⊖ E_ex, where E_ex is the subspace of eigenfunctions of T₁(Γ, 1) with eigenvalue λ such that |λ|=q+1. We present a construction of some finite homogeneous graphs such that the spectrum of their adjacency matrices can be calculated explicitly. Bibliography: 11 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 205, 1993, pp. 92–109. Translated by A. M. Nikitin.     

Homological identities for a finite homogeneous graph

An application of the Atiyah-Bott trace identity to the study of the spectral characteristics of a finite (q+1)-homogeneous factorgraph Y=Γ/X is given (X is an infinite (q+1)-homogeneous tree, Γ a free group of isometries of X). Bibliography: 9 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 205, 1993, pp. 110–121.     

The power graph on the conjugacy classes of a finite group

A digraph \({\overrightarrow{\mathcal{Pc}}(G)}\) is said to be the directed power graph on the conjugacy classes of a group G, if its vertices are the non-trivial conjugacy classes of G, and there is an arc from vertex C to C′ if and only if \({C \neq C'}\) and \({C \subseteqq {C'}^{m}}\) for some positive integer \({m > 0}\). Moreover, the simple graph \({\mathcal{Pc}(G)}\) is said to be the (undirected) power graph on the conjugacy classes of a group G if its vertices are the conjugacy classes of G and two distinct vertices C and C′ are adjacent in \({\mathcal{Pc}(G)}\) if one is a subset of a power of the other. In this paper, we find some connections between algebraic properties of some groups and properties of the associated graph.     

The swap graph of the finite soluble groups

A graph is reflexive if the second largest eigenvalue of its adjacency matrix is less than or equal to 2. In this paper, we characterize trees whose line graphs are reflexive. It turns out that these trees can be of arbitrary order—they can have either a unique vertex of arbitrary degree or pendant paths of arbitrary lengths, or both. Since the reflexive line graphs are Salem graphs, we also relate some of our results to the Salem (graph) numbers.     

On the intersection graph of a finite group

For a finite group G, the intersection graph of G which is denoted by Γ(G) is an undirected graph such that its vertices are all nontrivial proper subgroups of G and two distinct vertices H and K are adjacent when H ∩ K ≠ 1. In this paper we classify all finite groups whose intersection graphs are regular. Also, we find some results on the intersection graphs of simple groups and finally we study the structure of Aut(Γ(G)).     

The trace graph of the matrix ring over a finite commutative ring

Let R be a commutative ring and let \({n >1}\) be an integer. We introduce a simple graph, denoted by \({\Gamma_t(M_n(R))}\), which we call the trace graph of the matrix ring \({M_n(R)}\), such that its vertex set is \({M_n(R)^{\ast}}\) and such that two distinct vertices A and B are joined by an edge if and only if \({{\rm Tr} (AB)=0}\) where \({ {\rm Tr} (AB)}\) denotes the trace of the matrix AB. We prove that \({\Gamma_t(M_n(R))}\) is connected with \({{\rm diam}(\Gamma_{t}(M_{n}(R)))=2}\) and \({{\rm gr} (\Gamma_t(M_n(R)))=3}\). We investigate also the interplay between the ring-theoretic properties of R and the graph-theoretic properties of \({\Gamma_t(M_n(R))}\). Hence, we use the notion of the irregularity index of a graph to characterize rings with exactly one nontrivial ideal.     

On the power graph and the reduced power graph of a finite group

In this paper, for a finite group, we investigate to what extent its directed (resp. undirected) reduced power graph determines its directed power graph (resp. reduced power graph). Moreover, we investigate the determination of the orders of the elements of a finite group from its directed (resp. undirected) reduced power graph. Consequently, we show that some classes of finite groups are recognizable from their undirected reduced power graphs. Also, we study the relationship between the isomorphism classes of groups corresponding to the equivalence relations induced by the isomorphism of each of these graphs on the set of all finite groups.     

The finite integral transform method for a parabolic differential equation on a graph

The finite integral transform method is set forth and justified for solving a mixed problem for a parabolic differential equation posed on a graph.     

Riemann-Roch and Abel-Jacobi theory on a finite graph

It is well known that a finite graph can be viewed, in many respects, as a discrete analogue of a Riemann surface. In this paper, we pursue this analogy further in the context of linear equivalence of divisors. In particular, we formulate and prove a graph-theoretic analogue of the classical Riemann-Roch theorem. We also prove several results, analogous to classical facts about Riemann surfaces, concerning the Abel-Jacobi map from a graph to its Jacobian. As an application of our results, we characterize the existence or non-existence of a winning strategy for a certain chip-firing game played on the vertices of a graph.     

Reconstructing the number of copies of a valency-labeled finite graph in an infinite graph

Suppose that G, H are infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such that G - ξ ? H - Ψ(ξ) for every ξ ～ V(G). Let J be a finite graph and /(π) be a cardinal number for each π ? V(J). Suppose also that either /(π) is infinite for every π ? V(J) or J has a connected subgraph C such that /(π) is finite for every π ? V(C) and every vertex in V(J)/V(C) is adjacent to a vertex of C. Let (J, I, G) be the set of those subgraphs of G that are isomorphic to J under isomorphisms that map each vertex π of J to a vertex whose valency in G is /(π). We prove that the sets (J, I, G), m(J, I, H) have the same cardinality and include equal numbers of induced subgraphs of G, H respectively.     

The primitive conjugacy classes and the first homology group of a finite graph

The distribution of primitive conjugacy classes of the fundamental group of graphs in the first homology group of the graphs is studied in some special cases. Bibliography: 10 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 205, 1993, pp. 154–165. Translated by A. M. Nikitin.     

Infinite versus finite graph domination

We raise the following general problem: Which structural properties of dominating subgraphs in finite graphs remain valid for infinite graphs? Positive and negative results are presented.