On Hamiltonian-connected regular graphs

In this paper it is shown that any m-regular graph of order 2m (m ≧ 3), not isomorphic to K_m,m, or of order 2m + 1 (m even, m ≧ 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains atleast m Hamiltonian cycles for odd m and atleast 1/2m Hamiltonian cycles for even m.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

On regular self-complementary graphs

A regular self-complementary graph is presented which has no complementing permutation consisting solely of cycles of length four. This answers one of Kotzig's questions.     

On regular graphs,V

Let Γ₃ be an infinite regular tree of valence 3. There exist subgroups B of Aut (Γ₃) which are 5-regular on Γ₃, i.e., sharply transitive on the set of 5-arcs of Γ₃. We prove that any two such subgroups are conjugate in Aut (Γ₃). The pair (Γ₃, B) is a universal 5-regular action in the sense that if (G, A) is a pair consisting of a cubical graph G and a 5-regular subgroup A of automorphisms of G then (G, A) can be “covered” by (Γ₃, B) in a certain natural way.     

On regular graphs,VI

Let G be a connected regular graph of valence p + 1 where p is an odd prime. Let A be a subgroup of Aut(G) which is s-regular (s ≥ 0). We prove that s ≤ 3 and the cases s = 0, 1, 2, 3 do occur.     

On regular graphs. III

A graph G is locally s-regular if for any two s-arcs of G having the same head there exists a unique automorphism of G mapping the first of these s-arcs to the second. This is a natural generalization of the concept of an s-regular graph. We extend the results of [2] concerning s-regular graphs to this wider class. We also describe an example of a locally 7-regular cubic graph which is not 7-regular.     

On graphs with regular groups

A new method for the construction of graphs with given regular group is developed and used to show that to every nonabelian group G of order 3^k, k ≥ 4, there exists a graph X whose automorphism group is isomorphic to G and regular as a permutation group on the set of vertices of X.     

On nearly regular co-critical graphs

A graph G is called (K₃, K₃)-co-critical if the edges of G can be coloured with two colours without getting a monochromatic triangle, but adding any new edge to the graph, this kind of ‘good’ colouring is impossible. In this short note we construct (K₃, K₃)-co-critical graphs of maximal degree O(n^3/4).     

On regular graphs. IV

Let G be a connected combinatorial graph of valency p + 1 where p is an odd prime. Assume that there exists a group of automorphisms A of G whose induced action on the s-arcs of G is regular (sharply transitive). If s ≥ 2 we prove that p must be a Mersenne prime, i.e., of the form p = 2ⁿ ? 1. In general we know that s ≤ 5 or s = 7. We obtain some partial results when s = 7.     

On two-factors of bipartite regular graphs

The set of two-factors of a bipartite k-regular graph, k>2, spans the cycle space of the graph. In addition, a new non-hamiltonian 3-connected bicubic graph on 92 vertices is constructed.     

ON THE ASCENDING SUBGRAPH DECOMPOSITIONS OF REGULAR GRAPHS

The definition of the ascending suhgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.     

On products of graphs and regular groups

A graphX is called a graphical regular representation (GRR) of a groupG if the automorphism group ofX is regular and isomorphic toG. Watkins and Nowitz have shown that the direct productG×H of two finite groupsG andH has aGRR if both factors have aGRR and if at least one factor is different from the cyclic group of order two. We give a new proof of this result, thereby removing the restriction to finite groups. We further show that the complementX′ of a finite or infinite graphX is prime with respect to cartesian multiplication ifX is composite and not one of six exceptional graphs.     

On strongly regular self - complementary graphs

It is shown that certain conditions assumed on a regular self-complementary graph are not sufficient for the graph to be strongly regular, answering in the negative a question posed by Kotzig in [1].     

On 2-factor hamiltonian regular bipartite graphs

A k-regular bipartite graph is said to be 2-factor hamiltonian if each of its 2-factor is hamiltonian. It is well known that if a k-regular bipartite graph is 2-factor hamiltonian, then k?Q3. In this paper, we give a new proof of this fact.