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.     

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.     

On the well-coveredness of Cartesian products of graphs

A graph G is well-covered if every maximal independent set has the same cardinality. This paper investigates when the Cartesian product of two graphs is well-covered. We prove that if G and H both belong to a large class of graphs that includes all non-well-covered triangle-free graphs and most well-covered triangle-free graphs, then G×H is not well-covered. We also show that if G is not well-covered, then neither is G×G. Finally, we show that G×G is not well-covered for all graphs of girth at least 5 by introducing super well-covered graphs and classifying all such graphs of girth at least 5.     

NZ‐flows in strong products of graphs

We prove that the strong product G₁? G₂ of G₁ and G₂ is ?₃‐flow contractible if and only if G₁? G₂ is not T? K₂, where T is a tree (we call T? K₂ a K₄‐tree). It follows that G₁? G₂ admits an NZ 3 ‐flow unless G₁? G₂ is a K₄ ‐tree. We also give a constructive proof that yields a polynomial algorithm whose output is an NZ 3‐flow if G₁? G₂ is not a K₄ ‐tree, and an NZ 4‐flow otherwise. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 267–276, 2010     

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.     

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.     

1-Factorizations of cartesian products of regular graphs

Let G₁, G₂…, G_n be regular graphs and H be the Cartesian product of these graphs (H = G₁ × G₂ × … × G_n). The following will be proved: If the set {G₁, G₂…, G_n} has at leat one of the following properties: (*) for at leat one i ? {1, 2,…, n}, there exists a 1-factorization of G_i or (**) there exists at least two numbers i and j such that 1 ≤ i < j ≤ n and both the Graphs G_i and G_j contain at least one 1-factor, then there exists a 1-factorization of H. Further results: Let F be a cycle of length greater than three and let G be an arbitrary cubic graph. Then there exists a 1-factorization of the 5-regular graph H = F × G. The last result shows that neither (*) nor (**) is a necessary condition for the existence of a 1-factorization of a Cartesian product of regular graphs.     

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.     

A min-max theorem for plane bipartite graphs

We consider a partitioning problem, defined for bipartite and 2-connected plane graphs, where each node should be covered exactly once by either an edge or by a cycle surrounding a face. The objective is to maximize the number of face boundaries in the partition. This problem arises in mathematical chemistry in the computation of the Clar number of hexagonal systems. In this paper we establish that a certain minimum weight covering problem of faces by cuts is a strong dual of the partitioning problem. Our proof relies on network flow and linear programming duality arguments, and settles a conjecture formulated by Hansen and Zheng in the context of hexagonal systems [P. Hansen, M. Zheng, Upper Bounds for the Clar Number of Benzenoid Hydrocarbons, Journal of the Chemical Society, Faraday Transactions 88 (1992) 1621-1625].     

Inverse curvature flows in Riemannian warped products

The long-time existence and umbilicity estimates for compact, graphical solutions to expanding curvature flows are deduced in Riemannian warped products of a real interval with a compact fibre. Notably we do not assume the ambient manifold to be rotationally symmetric, nor the radial curvature to converge, nor a lower bound on the ambient sectional curvature. The inverse speeds are given by powers $0<p\le 1$ of a curvature function satisfying few common properties.     

A version of Brauer’s theorem for integer central functions

In this article we prove an effective version of the classical Brauer’s Theorem for integer class functions on finite groups.      

Homogeneous factorisations of graph products

A homogeneous factorisation of a digraph Γ consists of a partition P={P₁,…,P_k} of the arc set AΓ and two vertex-transitive subgroups M?G?Aut(Γ) such that M fixes each P_i setwise while G leaves P invariant and permutes its parts transitively. Given two graphs Γ₁ and Γ₂ we consider several ways of taking a product of Γ₁ and Γ₂ to form a larger graph, namely the direct product, cartesian product and lexicographic product. We provide many constructions which enable us to lift homogeneous factorisations or certain arc partitions of Γ₁ and Γ₂, to homogeneous factorisations of the various products.     

Bounded-excess flows in cubic graphs

An (r, α)-bounded-excess flow ((r, α)-flow) in an orientation of a graph G = (V, E) is an assignment f : E → [1, r−1], such that for every vertex x ∈ V, $|{\sum }_{e\in E^{+}\left(x\right)}f\left(e\right)-{\sum }_{e\in E^{-}\left(x\right)}f\left(e\right)|\le \alpha$. E⁺(x), respectively E⁻(x), is the set of edges directed from, respectively toward x. Bounded-excess flows suggest a generalization of Circular nowhere-zero flows (cnzf), which can be regarded as (r, 0)-flows. We define (r, α) as Stronger or equivalent to (s, β), if the existence of an (r, α)-flow in a cubic graph always implies the existence of an (s, β)-flow in the same graph. We then study the structure of the bounded-excess flow strength poset. Among other results, we define the Trace of a point in the r − α plane by $tr\left(r,\alpha \right)=\frac{r-2\alpha }{1-\alpha }$ and prove that among points with the same trace the stronger is the one with the smaller α (and larger r). For example, if a cubic graph admits a k-nzf (trace k with α = 0), then it admits an $(r,\frac{k-r}{k-2})$-flow for every r, 2 ≤ r ≤ k. A significant part of the article is devoted to proving the main result: Every cubic graph admits a $(3\frac{1}{2},\frac{1}{2})$-flow, and there exists a graph which does not admit any stronger bounded-excess flow. Notice that $tr(3\frac{1}{2},\frac{1}{2})=5$ so it can be considered a step in the direction of the 5-flow Conjecture. Our result is the best possible for all cubic graphs while the seemingly stronger 5-flow Conjecture relates only to bridgeless graphs. We also show that if the circular-flow number of a cubic graph is strictly less than 5, then it admits a $(3\frac{1}{3},\frac{1}{3})$-flow (trace 4). We conjecture such a flow to exist in every cubic graph with a perfect matching, other than the Petersen graph. This conjecture is a stronger version of the Ban-Linial Conjecture [1]. Our work here strongly relies on the notion of Orientable k-weak bisections, a certain type of k-weak bisections. k-Weak bisections are defined and studied by L. Esperet, G. Mazzuoccolo, and M. Tarsi [4].     

A polynomial algorithm for integer programming covering problems satisfying the integer round-up property

LetA be a non-negative matrix with integer entries and no zero column. The integer round-up property holds forA if for every integral vectorw the optimum objective value of the generalized covering problem min{1y: yA w, y 0 integer} is obtained by rounding up to the nearest integer the optimum objective value of the corresponding linear program. A polynomial time algorithm is presented that does the following: given any generalized covering problem with constraint matrixA and right hand side vectorw, the algorithm either finds an optimum solution vector for the covering problem or else it reveals that matrixA does not have the integer round-up property.     

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.