Isomorphic factorizations VII. Regular graphs and tournaments

It is shown using enumeration results that for r > 2t, almost all labeled r-regular graphs cannot be factorized into t ? 2 isomorphic subgraphs. However, no examples of such nonfactorizable graphs are known which satisfy the obvious divisibility condition that the number of edges is divisible by t. Similar observations hold for regular tournaments (t ? 2} and for r-regular digraphs (r > t ? 2).     

Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs

We construct 3-regular (cubic) graphs G that have a dominating cycle C such that no other cycle C₁ of G satisfies V(C) ? V(C₁). By a similar construction we obtain loopless 4-regular graphs having precisely one hamiltonian cycle. The basis for these constructions are considerations on the uniqueness of a cycle decomposition compatible with a given eulerian trail in some eulerian graph.     

Hamiltonian decomposition of Cayley graphs of ordersp 2 andpq

In this paper, it is proved that any connected Cayley graph on an abelian group of order pq orp ² has a hamiltonian decomposition, wherep andq are odd primes. This result answers partially a conjecture of Alspach concerning hamiltonian decomposition of 2k-regular connected Cayley graphs on abelian groups.     

Graphs with homeomorphically irreducible spanning trees

It is an NP-complete problem to decide whether a graph contains a spanning tree with no vertex of degree 2. We show that these homeomorphically irreducible spanning trees are contained in all graphs with minimum degree at least c√n and in triangulations of the plane. They are nearly present in all graphs of diameter 2. They do not necessarily occur in r-regular or r-connected graphs.     

Graphs of arbitrary excessive class

We show that there exists a family of r-regular graphs of arbitrarily large excessive index for each integer r greater than 3. Furthermore, we answer a question in Bonisoli and Cariolaro (2007) [1] showing that all the positive integers can be attained as excessive classes of regular graphs.     

3-star factors in random -regular graphs

The small subgraph conditioning method first appeared when Robinson and the second author showed the almost sure hamiltonicity of random d-regular graphs. Since then it has been used to study the almost sure existence of, and the asymptotic distribution of, regular spanning subgraphs of various types in random d-regular graphs and hypergraphs. In this paper, we use the method to prove the almost sure existence of 3-star factors in random d-regular graphs. This is essentially the first application of the method to non-regular subgraphs in such graphs.     

Hamiltonian cycles in random regular graphs

The existence of Hamiltonian cycles in random vertex-labelled regular graphs is investigated. It is proved that there exists r₀≤796 such that for r≥r₀ almost all vertex-labelled r-regular graphs with n vertices have Hamiltonian cycles as n → ∞.     

Independent dominating sets and hamiltonian cycles

A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r‐regular uniquely hamiltonian graphs when r > 22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233–244, 2007     

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.     

On the independence number of random cubic graphs

We show that as n→∞, the independence number α(G), for almost all 3-regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ?)n, for any constant ?>0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley & Sons, Inc.     

Parameterized Algorithms in Smooth 4-Regular Hamiltonian Graphs

Smooth 4-regular hamiltonian graphs are generalizations of cycle plus triangles graphs. It has been shown that both the independent set and 3-colorability problems are NP-Complete in this class of graphs. In this paper we show that these problems are fixed parameter tractable if we choose the number of inner cycles as parameter. The reseach has been supported by International Science Programme (ISP) of Sweden, under the project titled “The Eastern African Universities Mathematics Programme (EAUMP)”.     

Regular factors of regular graphs

Given r ? 3 and 1 ? λ ? r, we determine all values of k for which every r-regular graph with edge-connectivity λ has a k-factor.     

On 3-regular 4-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian), if for any sequence of k distinct vertices v₁,…,v_kof G there exists a cycle (respectively, hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability and posed the question of the existence of 3-regular 4-ordered (hamiltonian) graphs other than K₄ and K_3,3. Ng and Schultz observed that a 3-regular 4-ordered graph on more than 4 vertices is triangle free. We prove that a 3-regular 4-ordered graph G on more than 6 vertices is square free,and we show that the smallest graph that is triangle and square free, namely the Petersen graph, is 4-ordered. Furthermore, we prove that the smallest graph after K₄ and K_3,3 that is 3-regular 4-ordered hamiltonianis the Heawood graph. Finally, we construct an infinite family of 3-regular 4-ordered graphs.     

Almost all Cayley graphs are hamiltonian

It has been conjectured that there is a hamiltonian cycle in every finite connected Cayley graph. In spite of the difficulty in proving this conjecture, we show that almost all Cayley graphs are hamiltonian. That is, as the order n of a groupG approaches infinity, the ratio of the number of hamiltonian Cayley graphs ofG to the total number of Cayley graphs ofG approaches 1.Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University.     

Modularity in random regular graphs and lattices

Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity of G is the maximum modularity of a partition.We give an upper bound on the modularity of r-regular graphs as a function of the edge expansion (or isoperimetric number) under the restriction that each part in our partition has a sub-linear numbers of vertices. This leads to results for random r-regular graphs. In particular we show the modularity of a random cubic graph partitioned into sub-linear parts is almost surely in the interval (0.66, 0.88).The modularity of a complete rectangular section of the integer lattice in a fixed dimension was estimated in Guimer et. al. [R. Guimerà, M. Sales-Pardo and L.A. Amaral, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E 70 (2) (2004) 025101]. We extend this result to any subgraph of such a lattice, and indeed to more general graphs.     

New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].     

Edge-Colorings of 4-Regular Graphs with the Minimum Number of Palettes

A proper edge-coloring of a graph G is an assignment of colors to the edges of G such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Horňák, Kalinowski, Meszka and Wo?niak, we call such a set of colors the palette of the vertex. What is the minimum number of distinct palettes taken over all proper edge-colorings of G? A complete answer is known for complete graphs and cubic graphs. We study in some detail the problem for 4-regular graphs. In particular, we show that certain values of the palette index imply the existence of an even cycle decomposition of size 3 (a partition of the edge-set of a graph into 3 2-regular subgraphs whose connected components are cycles of even length). This result can be extended to 4d-regular graphs. Moreover, in studying the palette index of a 4-regular graph, the following problem arises: does there exist a 4-regular graph whose even cycle decompositions cannot have size smaller than 4?     

Hamiltonian weights and unique 3-edge-colorings of cubic graphs

A (1,2)-eulerian weight w of a grph is hamiltonian if every faithful cover of w is a set of two Hamilton circuits. Let G be a 3-connected cubic graph containing no subdivition of the Petersen graph. We prove that if G admits a hamiltonian weight then G is uniquely 3-edge-colorable. © 1996 John Wiley & Sons, Inc.     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.