Construction of a certain class of line graphs

The construction of a line graph is described on the basis of a finite bipartite graph, for a given k > 1. An algorithm is set forth for the construction of the line graph and an example of its use is given.Translated from Dinamicheskie Sistemy, No. 4, pp. 107–116, 1985.     

Fixed-edge theorem for graphs with loops

Let G be an undirected graph without multiple edges and with a loop at every vertex—the set of edges of G corresponds to a reflexive and symmetric binary relation on its set of vertices. Then every edge-preserving map of the set of vertices of G to itself fixes an edge [{f(a), f(b)} = {a, b} for some edge (a, b) of G] if and only if (i) G is connected, (ii) G contains no cycles, and (iii) G contains no infinte paths. The proof is conerned with those subgraphs H of a graph G for which there is an edge-preserving map f of the set of vertices of G onto the set of vertices of H and satisfying f(a) = a for each vertex a of H.     

Cartesian products of directed graphs with loops

We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space.     

Multiples of left loops and vertex-transitive graphs

Via representation of vertex-transitive graphs on groupoids, we show that left loops with units are factors of groups, i.e., left loops are transversals of left cosets on which it is possible to define a binary operation which allows left cancellation.     

Construction of class 2 graphs with maximum vertex degree 3

A new method is developed for constructing graphs with maximum vertex degree 3 and chromatic index 4. In particular an infinite family of edge-critical graphs with an even number of vertices is constructed; this disproves the Critical Graph Conjecture.     

On elementary theories of graphs and Abelian loops

The algorithmic decidability of elementary theories of certain classes of graphs, such as homogeneous, planar, bipartite planar, and critical nonplanar, is discussed. For the first three classes we prove the undecidability of elementary theories, and for the last, decidability with a supplementary predicate. We also prove the undecidability of theory of Abelian loops by an interpretation in it of theory of bipartite homogeneous 3rd degree graphs.Translated from Matematicheskie Zametki, Vol. 16, No. 6, pp. 957–968, December, 1974.     

Nilpotent Steiner loops of class 2

We describe Steiner loops of nilpotency class 2 and establish the classification of finite 3-generated nilpotent Steiner loops of nilpotency class 2.     

SOME PROPERTIES OF A CLASS OF INTERCHANGE GRAPHS

§１ＩｎｔｒｏｄｕｃｔｉｏｎＬｅｔＧｂｅａｃｏｎｎｅｃｔｅｄｇｒａｐｈｗｉｔｈｖｅｒｔｅｘ－ｓｅｔＶ（Ｇ）ａｎｄｅｄｇｅ－ｓｅｔＥ（Ｇ）．Ｄｅｎｏｔｅｂｙｅ＝（ｘ，ｙ）ｔｈｅｅｄｇｅｊｏｉｎｉｎｇｔｈｅｖｅｒｔｉｃｅｓｘａｎｄｙｏｆＧ．Ａｍ－ｃｌｉｑ...     

The complexity of a class of infinite graphs

IfG _k is the family of countable graphs with nok vertex (or edge) disjoint circuits (1<k<) then there is a countableG _k G _k such that every member ofG _k is an (induced) subgraph of some member ofG _k , but no finiteG _k suffices.     

Orientably-regular embeddings of a class of multipartite graphs

The orientably-regular embeddings of complete multipartite graphs have been determined by the contributions of several papers. After that, a natural question can be asked: How about the regular embeddings of the multipartite graphs with m parts, while each part contains n vertices(not necessarily complete multipartite). In this paper, we classify all the orientably-regular embeddings of these graphs when m is a prime q and n is a prime power pe.     

Extension of a class of fibered loops to kinematic spaces

The notion of the split extension of a commutative kinematic space is extended to the case of a weak K-loop with an incidence fibration (F, +, ). Theorem 1 states conditions under wich the quasi-direct productG F⁺ _Q with Aut(F, +) can be turned in a fibered incidence group (G, , o) such that (F, +, ) becomes embeddable inG, and Theorem 2 the additional assumption such that (G, , o) is even a kinematic space. In section 4, Theorem 3 shows that there are suitable examples of proper K-loops with an incidence fibration (derived from hyperbolic planes) on which one can apply Theorem 2.Dedicated to Erich Ellers on the occasion of his 70th birthdayResearch supported by M.U.R.S.T. 40% and by C.N.R. (G.N.S.A.G.A.)     

On a class of graphs without 3-stars

M. Numata described edge regular graphs without 3-stars. Allμ-subgraphs of these graphs are regular of the same valency. We prove that a connected graph without 3-stars all of whoseμ- subgraphs are regular of valencyα > 0 is either a triangular graph, or the Shläfli graph, or the icosahedron graph.     

Minimizer graphs for a class of extremal problems

We consider the family of graphs with a fixed number of vertices and edges. Among all these graphs, we are looking for those minimizing the sum of the square roots of the vertex degrees. We prove that there is a unique such graph, which consists of the largest possible complete subgraph plus only one other non‐isolated vertex. The same result is proven for any power of the vertex‐degrees less than one half. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 230–240, 2002; DOI 10.1002/jgt.10025     

Some properties for a class of interchange graphs

The Wiener number is the sum of distances between all pairs of vertices of a connected graph. In this paper, we give an explicit algebraic formula for the Wiener number of a class of interchange graphs. Moreover, distance-related properties and cliques of this class of interchange graphs are investigated.     

Enumeration of nilpotent loops via cohomology

The isomorphism problem for centrally nilpotent loops can be tackled by methods of cohomology. We develop tools based on cohomology and linear algebra that either lend themselves to direct count of the isomorphism classes (notably in the case of nilpotent loops of order 2q, q a prime), or lead to efficient classification computer programs. This allows us to enumerate all nilpotent loops of order less than 24.     

A class of simple proper Bol loops

The existence of finite simple non-Moufang Bol loops has long been considered to be one of the main open problems in the theory of loops and quasigroups. In this paper, we present a class of simple proper Bol loops. This class contains finite and new infinite simple proper Bol loops. This paper was written during the author’s Marie Curie Fellowship MEIF-CT-2006-041105 at the University of Würzburg (Germany).