1-Factorizations of random regular graphs

It is shown that for each r ≥ 3, a random r-regular graph on 2n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2n vertices, as n → ∞. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almost sure in one sequence of spaces are almost sure in the other, and vice versa. The corresponding statement is also shown for bipartite graphs, and from this it is shown that a random r-regular simple digraph is almost surely strongly r-connected for all r ≥ 2. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 305–321 (1997)     

Nonorientable genus of cartesian products of regular graphs

A special type of surgery developed by A. T. White and later used by the author to construct orientable quadrilateral embeddings of Cartesian products of graphs is here expanded to cover the nonorientable case as well. This enables the nonorientable genus of many families of Cartesian products of triangle-free graphs to be computed.     

Genus of cartesian products of regular bipartite graphs

Let G(n, d) denote a connected regular bipartite graph on 2n vertices and of degree d. It is proved that any Cartesian product G(n, d) × G₁(n₁, d₁) × G₂(n₂, d₂) × ? × G_m(n_m, d_m), such that max {d₁, d₂,…, d_m} ≤ d ≤ d₁ + d₂ + ? + d_m, has a quadrilateral embedding, thereby establishing its genus, and thereby generalizing a result of White. It is also proved that if G is any connected bipartite graph of maximum degree D, if Q_m is the m-cube graph, and if m ≥ D then G × Q_m has a quadrilateral embedding.     

Fall colouring of bipartite graphs and cartesian products of graphs

The question of whether a graph can be partitioned into k independent dominating sets, which is the same as having a fallk-colouring, is considered. For k=3, it is shown that a graph G can be partitioned into three independent dominating sets if and only if the cartesian product G□K₂ can be partitioned into three independent dominating sets. The graph K₂ can be replaced by any graph H such that there is a mapping f:Q_n→H, where f is a type-II graph homomorphism.The cartesian product of two trees is considered, as well as the complexity of partitioning a bipartite graph into three independent dominating sets, which is shown to be NP-complete. For other values of k, iterated cartesian products are considered, leading to a result that shows for what values of k the hypercubes can be partitioned into k independent dominating sets.     

Embeddings of cartesian products of nearly bipartite graphs

Surgical techniques are often effective in constructing genus embeddings of cartesian products of bipartite graphs. In this paper we present a general construction that is “close” to a genus embedding for cartesian products, where each factor is “close” to being bipartite. In specializing this to repeated cartesian products of odd cycles, we are able to obtain asymptotic results in connection with the genus parameter for finite abelian groups.     

Hamiltonicity and pancyclicity of cartesian products of graphs

The cartesian product of a graph G with K₂ is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g^′(H) and Δ(H)≤g^′(G) (we denote by g^′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian.     

A theorem on integer flows on cartesian products of graphs

It is shown that the Cartesian product of two nontrivial connected graphs admits a nowhere‐zero 4‐flow. If both factors are bipartite, then the product admits a nowhere‐zero 3‐flow. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 93–98, 2003     

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.     

ContributionsOn optimal orientations of cartesian products of graphs (I)

For a graph G, let D(G) be the family of strong orientations of G, and define [ovbar|d] (G) = min[d(D) vb D ] D(G), where d(D) denotes the diameter of the digraph D. Let G × H denote the cartesian product of the graphs G and H. In this paper, we determine completely the values of and , except , where K_n, P_n and C_n denote the complete graph, path and cycle of order n, respectively.     

Stability of cartesian products

We complete the work started by Holton and Grant concerning the semi-stability of non-trivial connected cartesian products and show that all such products are semi-stable. Further we show that except for certain (listed) restricted graphs, connected cartesian products are semi-stable at every vertex. Finally, we show that the cartesian product of any two graphs is not semi-stable if and only if one of them is totally disconnected and the other is not semi-stable.     

1-factor covers of regular graphs

We consider minimal 1-factor covers of regular multigraphs, focusing on those that are 1-factorizations. In particular, we classify cubic graphs such that every minimal 1-factor cover is also a 1-factorization, and also classify simple regular bipartite graphs with this property. For r>3, we show that there are finitely many simple r-regular graphs such that every minimal 1-factor cover is also a 1-factorization.     

s-strongly perfect cartesian product of graphs

The study of perfectness, via the strong perfect graph conjecture, has given rise to numerous investigations concerning the structure of many particular classes of perfect graphs. In “Perfect Product Graphs” (Discrete Mathematics, Vol. 20, 1977, pp. 177--186), G. Ravindra and K. R. Parthasarathy tried, but unfortunately without success, to characterize the perfectness of the cartesian product of graphs (see also MR No. 58--10567, 1979). In this paper we completely characterize the graphs that are both nontrivial cartesian products and s-strongly perfect.     

Fair 1-Factorizations and Fair Holey 1-Factorizations of Complete Multipartite Graphs

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If \(V_{1},\ldots , V_{p}\) are the p parts of V(K(n, p)), then a holey k -factor of deficiency \(V_{i}\) of K(n, p) is a k-factor of \(K(n,p)-V_{i}\) for some i satisfying \(1\le i \le p\). Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared “evenly” among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each \(n \times n\) “box”. These quasigroups are in some sense as far from frames produced by direct products as possible.     

Strongly regular graphs with λ=1

Translated from Matematicheskie Zametki, Vol. 44, No. 5, pp. 667–672, November, 1988.     

Strongly regular graphs

In this paper we have tried to summarize the known results on strongly regular graphs. Both groupal and combinatorial aspects of the theory have been included. We give the list of all known strongly regular graphs and a large bibliography of this subject.     

Hamilton decompositions of cartesian products of multicycles

We define the multicycle C^(r)_m as a cycle on m vertices where each edge has multiplicity r. So C^(r)_m can be decomposed into r Hamilton cycles. We provide a complete answer to the following question: for which positive integers m, n, r, s with m, n ≥ 3 can the Cartesian product of two multicycles C^(r)_m x C^(s)_n be decomposed into r + s Hamilton cycles? We find some interesting characterizations of Hamilton cycles of C_m x C_n while answering the above question. © 1997 John Wiley & Sons, Inc.     

Factorization of regular multigraphs into regular graphs

A regular multigraph with maximum multiplicity r and degree rs cannot always be factored into r s-regular simple graphs. It is shown, however, that under general conditions a similar factorization can be achieved if we first allow the addition or deletion of a relatively small number of hamilton cycles. Based on this result, we give extensions of some known factorization results on simple graphs to new results on multigraphs. © 1995 John Wiley & Sons, Inc.