Eulerian edge sets in locally finite graphs

In a finite graph, an edge set Z is an element of the cycle space if and only if every vertex has even degree in Z. We extend this basic result to the topological cycle space, which allows infinite circuits, of locally finite graphs. In order to do so, it becomes necessary to attribute a parity to the ends of the graph.     

Isomorphisms of finite semi-Cayley graphs

Let G be a finite group. A Cayley graph over G is a simple graph whose automorphism group has a regular subgroup isomorphic to G. A Cayley graph is called a CI-graph(Cayley isomorphism) if its isomorphic images are induced by automorphisms of G. A well-known result of Babai states that a Cayley graph Γ of G is a CI-graph if and only if all regular subgroups of Aut(Γ) isomorphic to G are conjugate in Aut(Γ). A semi-Cayley graph(also called bi-Cayley graph by some authors) over G is a simple graph whose automorphism group has a semiregular subgroup isomorphic to G with two orbits(of equal size). In this paper, we introduce the concept of SCI-graph(semi-Cayley isomorphism)and prove a Babai type theorem for semi-Cayley graphs. We prove that every semi-Cayley graph of a finite group G is an SCI-graph if and only if G is cyclic of order 3. Also, we study the isomorphism problem of a special class of semi-Cayley graphs.     

Algebraic Cayley graphs over finite local rings

In this work, we define and study the algebraic Cayley directed graph over a finite local ring. Its vertex set is the unit group of a finite extension of a finite local ring R and its adjacency condition is that the quotient is a monic primary polynomial. We investigate its connectedness and diameter bound, and we also show that our graph is an expander graph. In addition, if a local ring has nilpotency two, then we obtain a better view of our graph from the lifting of the graph over its residue field.     

Complexity of computation in finite fields

We give a review of some works on the complexity of implementation of arithmetic operations in finite fields by Boolean circuits.     

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.     

Critical groups for homeomorphism classes of graphs

In this paper the weighted fundamental circuits intersection matrix of an edge-labeled graph is introduced for computing the critical groups for homeomorphism classes of graphs. As an application, it is proved that for any given finite connected simple graph there is a homeomorphic graph with cyclic critical group.     

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 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.     

A natural graph of finite fields distinguishing between models

We define a graph structure associated in a natural way to finite fields that nevertheless distinguishes between different models of isomorphic fields. Certain basic notions in finite field theory have interpretations in terms of standard graph properties. We show that the graphs are connected and provide an estimate of their diameter. An accidental graph isomorphism is uncovered and proved. The smallest non-trivial Laplace eigenvalue is given some attention, in particular for a specific family of 8-regular graphs showing that it is not an expander. We introduce a regular covering graph and show that it is connected if and only if the root is primitive.     

Single-hook characters and hamiltonian circuits

This paper consider coefficients. schur functions, immanants and graph theory. The connecting thread is the concept of a single-hook character of the symmetric group. It is shown, for example, that the number of Hamiltonian circuits in a finite graph may be expressed as an alternating sum of immanants.     

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.     

Recognition of finite groups by the prime graph

We obtain the first example of an infinite series of finite simple groups that are uniquely determined by their prime graph in the class of all finite groups. We also show that there exist almost simple groups for which the number of finite groups with the same prime graph is equal to 2. Supported by RFBR grant No. 05-01-00797, and by SB RAS Young Researchers Support grant No. 29 and Integration project No. 2006.1.2. __________ Translated from Algebra i Logika, Vol. 45, No. 4, pp. 390–408, July–August, 2006.     

Embedding arbitrary finite simple graphs into small strongly regular graphs

It is well known that any finite simple graph Γ is an induced subgraph of some exponentially larger strongly regular graph Γ (e.g., [2, 8]). No general polynomial‐size construction has been known. For a given finite simple graph Γ on υ vertices, we present a construction of a strongly regular graph Γ on O(υ⁴) vertices that contains Γ as its induced subgraph. A discussion is included of the size of the smallest possible strongly regular graph with this property. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 1–8, 2000     

On end degrees and infinite cycles in locally finite graphs

We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.     

On locally primitive Cayley graphs of finite simple groups

In this paper we investigate locally primitive Cayley graphs of finite nonabelian simple groups. First, we prove that, for any valency d for which the Weiss conjecture holds (for example, d?20 or d is a prime number by Conder, Li and Praeger (2000) [1]), there exists a finite list of groups such that if G is a finite nonabelian simple group not in this list, then every locally primitive Cayley graph of valency d on G is normal. Next we construct an infinite family of p-valent non-normal locally primitive Cayley graph of the alternating group for all prime p?5. Finally, we consider locally primitive Cayley graphs of finite simple groups with valency 5 and determine all possible candidates of finite nonabelian simple groups G such that the Cayley graph Cay(G,S) might be non-normal.     

Decomposition of infinite eulerian graphs with a small number of vertices of infinite degree

We consider the question whether an infinite eulerian graph has a decomposition into circuits and rays if the graph has only finitely many, say n, vertices of infinite degree, and only finitely many finite components after the removal of the vertices of infinite degree. It is known that the answer is affirmative for n2 and negative for n4. We settle the remaining case n=3, showing that a decomposition into circuits and rays also exists in this case.     

An edge-deletion problem for locally finite graphs

For each positive integer n, let T_n be the tree in which exactly one vertex has degree n and all the other vertices have degree n + 1. A graph G is called stable if its edge set is nonempty and if deleting an arbitrary edge of G there is always a component of the residue graph which is isomorphic to G. The question whether there are locally finite stable graphs that are not isomorphic to one of the graphs T_n is answered affirmatively by constructing an uncountable family of pairwise nonisomorphic, locally finite, stable graphs. Further, the following results are proved: (1) Among the locally finite trees containing no subdivision of T₂, the oneway infinite path T₁ is the only stable graph. (2) Among the locally finite graphs containing no two-way infinite path, T₁ is also the only stable graph.     

On the representation of finite multiple Markov chains by weighted circuits

In this paper circuit chains of superior order are defined as multiple Markov chains for which transition probabilities are expressed in terms of the weights of a finite class of circuits in a finite set, in connection with kinetic properties along the circuits. Conversely, it is proved that if we join any finite doubly infinite strictly stationary Markov chain of order r for which transitions hold cyclically with a second chain with the same transitions for the inverse time-sense, then they may be represented as circuit chains of order r.