On the fastest moving off from a vertex in directed regular graphs

Let Γ be a directed regular locally finite graph, and let $\bar \Gamma $ be the undirected graph obtained by forgetting the orientation of Γ. Let x be a vertex of Γ and let n be a nonnegative integer. We study the length of the shortest directed path in Γ starting at x and ending outside of the ball of radius n centered at x in $\bar \Gamma $ .     

On the hamiltonicity of line graphs of locally finite, 6‐edge‐connected graphs

The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a weaker version of this result for infinite graphs: The line graph of locally finite, 6‐edge‐connected graph with a finite number of ends, each of which is thin, is hamiltonian.     

The vertex-transitive TLF-planar graphs

We consider the class of the topologically locally finite (in short TLF) planar vertex-transitive graphs. We characterize these graphs by finite combinatorial objects called labeling schemes. As a result, we are able to enumerate and describe all TLF-planar vertex-transitive graphs of given degree, as well as most of their transitive groups of automorphisms. In addition,we are able to decide whether a given TLF-planar transitive graph is Cayley or not. This class contains all the one-ended planar Cayley graphs and the normal transitive tilings of the plane.     

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.     

An Adjacency Criterion for the Prime Graph of a Finite Simple Group

For every finite non-Abelian simple group, we give an exhaustive arithmetic criterion for adjacency of vertices in a prime graph of the group. For the prime graph of every finite simple group, this criterion is used to determine an independent set with a maximal number of vertices and an independent set with a maximal number of vertices containing 2, and to define orders on these sets; the information obtained is collected in tables. We consider several applications of these results to various problems in finite group theory, in particular, to the recognition-by-spectra problem for finite groups. Supported by RFBR grant No. 05-01-00797; by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1; by the RF Ministry of Education Developmental Program for Scientific Potential of the Higher School of Learning, project No. 8294; by FP “Universities of Russia,” grant No. UR.04.01.202; and by Presidium SB RAS grant No. 86-197. __________ Translated from Algebra i Logika, Vol. 44, No. 6, pp. 682–725, November–December, 2005.     

Locally primitive Cayley graphs of finite simple groups

A graph Г is said to be G-locally primitive, where G is a subgroup of automorphisms of Г, if the stabiliser G_a of a vertex α acts primitively on the set Г( α ) of vertices of Г adjacent to α. For a finite non-abelian simple group L and a Cayley subset S of L, suppose that L ⊴ G ⩽ Aut( L), and the Cayley graph Г = Cay ( L, S) is G-locally primitive. In this paper we prove that L is a simple group of Lie type, and either the valency of Г is an add prine divisor of |Out(L)|, orL =PΩ ₈ ⁺ (q) and Г has valency 4. In either cases, it is proved that the full automorphism group of Г is also almost simple with the same socle L.     

On Connection Between the Structure of a Finite Group and the Properties of Its Prime Graph

It is shown that the condition of nonadjacency of 2 and at least one odd prime in the Gruenberg-Kegel graph of a finite group G under some natural additional conditions suffices to describe the structure of G; in particular, to prove that G has a unique nonabelian composition factor. Applications of this result to the problem of recognition of finite groups by spectrum are also considered.Original Russian Text Copyright © 2005 Vasilev A. V.The author was supported by the Russian Foundation for Basic Research (Grant 05-01-00797), the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant NSh-2069.2003.1), the Program Development of the Scientific Potential of Higher School of the Ministry for Education of the Russian Federation (Grant 8294), the Program Universities of Russia (Grant UR.04.01.202), and a grant of the Presidium of the Siberian Branch of the Russian Academy of Sciences (No. 86-197).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 3, pp. 511–522, May–June, 2005.     

Intersection models of weakly chordal graphs

We first present new structural properties of a two-pair in various graphs. A two-pair is used in a well-known characterization of weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal ()-free graph if and only if G is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4, 4, 2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain an algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4, 4, 2] graphs.     

Graph-like compacta: Characterizations and Eulerian loops

A compact graph-like space is a triple $\left(X,V,E\right)$, where $X$ is a compact, metrizable space, $V\subseteq X$ is a closed zero-dimensional subset, and $E$ is an index set such that $X⧹V\cong \text{◂+▸}E\times \left(0,1\right)$. New characterizations of compact graph-like spaces are given, connecting them to certain classes of continua, and to standard subspaces of Freudenthal compactifications of locally finite graphs. These are applied to characterize Eulerian graph-like compacta.     

A Local Analysis of Imprimitive Symmetric Graphs

Let Г be a G-symmetric graph admitting a nontrivial G-invariant partition . Let Г be the quotient graph of Г with respect to . For each block B ∊ , the setwise stabiliser G_B of B in G induces natural actions on B and on the neighbourhood Г (B) of B in Г . Let G_(B) and G_[B] be respectively the kernels of these actions. In this paper we study certain “local actions" induced by G_(B) and G_[B], such as the action of G_[B] on B and the action of G_(B) on Г (B), and their influence on the structure of Г. Supported by a Discovery Project Grant (DP0558677) from the Australian Research Council and a Melbourne Early Career Researcher Grant from The University of Melbourne.     

Global gradient estimate on graph and its applications

Continuing our previous work(ar Xiv:1509.07981v1),we derive another global gradient estimate for positive functions,particularly for positive solutions to the heat equation on finite or locally finite graphs.In general,the gradient estimate in the present paper is independent of our previous one.As applications,it can be used to get an upper bound and a lower bound of the heat kernel on locally finite graphs.These global gradient estimates can be compared with the Li–Yau inequality on graphs contributed by Bauer et al.[J.Differential Geom.,99,359–409(2015)].In many topics,such as eigenvalue estimate and heat kernel estimate(not including the Liouville type theorems),replacing the Li–Yau inequality by the global gradient estimate,we can get similar results.     

Geodetic rays and fibers in periodic graphs

Using the notion of fibers, where two rays belong to the same fiber if and only if they lie within bounded Hausdorff‐distance of one another, we study how many fibers of a graph contain a geodetic ray and how many essentially distinct geodetic rays such “geodetic fibers” must contain. A complete answer is provided in the case of locally finite graphs that admit an almost transitive action by some infinite finitely generated, abelian group. Such graphs turn out to have either finitely many or uncountably many geodetic fibers. Furthermore, with finitely many possible exceptions, each of these fibers contains uncountably many geodetic rays. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 67–88, 2000     

On recognition of finite simple groups with connected prime graph

The spectrum of a finite group is the set of its element orders. We prove a theorem on the structure of a finite group whose spectrum is equal to the spectrum of a finite nonabelian simple group. The theorem can be applied to solving the problem of recognizability of finite simple groups by spectrum.     

On Locally Projective Graphs of Girth 5

Let be a graph and G be a 2-arc transitive automorphism group of . For a vertex x let G(x)^(x) denote the permutation group induced by the stabilizer G(x) of x in G on the set (x) of vertices adjacent to x in . Then is said to be a locally projective graph of type (n,q) if G(x)^(x) contains PSL_n(q) as a normal subgroup in its natural doubly transitive action. Suppose that is a locally projective graph of type (n,q), for some n 3, whose girth (that is, the length of a shortest cycle) is 5 and suppose that G(x) acts faithfully on (x). (The case of unfaithful action was completely settled earlier.) We show that under these conditions either n=4, q=2, has 506 vertices and , and contains the Wells graph on 32 vertices as a subgraph. In the latter case if, for a given n, at least one graph satisfying the conditions exists then there is a universal graph W(n) of which all other graphs for this n are quotients. The graph W(3) satisfies the conditions and has 2²⁰ vertices.     

Groups which Are Factorized by Subgroups of Finite Exponents

New results on groups factorizable by permutable subgroups are established. Dedicated to the 70^th birthday anniversary of the outstanding algebraist and my teacher Prof. Vladimir Petrovich ShunkovMathematics Subject Classification (2000) 20E15.     

A new characterization of Suzuki-Ree group

It is proved that a Suzuki-Ree group can he characterized by the bet of its order components Project partially supported by the National Natural Science Foundation of China and Ph. D. Foundation of Southwest China Normal University.     

Extending colorings of locally planar graphs

Suppose G is a graph embedded in S_g with width (also known as edge width) at least 264(2^g−1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5‐coloring of P extends to a 5‐coloring of all of G. We present similar extension theorems for 6‐ and 7‐chromatic toroidal graphs, for 3‐colorable large‐width graphs embedded on S_g with every face even‐sided, and for 4‐colorable large‐width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001     

局部有限超拓扑的局部紧性

本文讨论了赋予局部有限拓扑的非空闲子集超空间的局部紧性.主要结果是:X正则,则其闭子集超空间局部紧当且仅当X可表示成一个紧空间与一个离散空间的拓扑和.     

The Cayley graphs of ℤ<Superscript>d</Superscript> and the limits of vertex-primitive graphs of <Emphasis Type="Italic">HA</Emphasis>-type

We study the limits of the finite graphs that admit some vertex-primitive group of automorphisms with a regular abelian normal subgroup. It was shown in [1] that these limits are Cayley graphs of the groups ?^d. In this article we prove that for each d > 1 the set of Cayley graphs of ?^d presenting the limits of finite graphs with vertex-primitive and edge-transitive groups of automorphisms is countable (in fact, we explicitly give countable subsets of these limit graphs). In addition, for d < 4 we list all Cayley graphs of ?^d that are limits of minimal vertex-primitive graphs. The proofs rely on a connection of the automorphism groups of Cayley graphs of ?^d with crystallographic groups.