Nowhere‐zero flows in tensor product of graphs

In this paper, we characterize graphs whose tensor product admit nowhere‐zero 3‐flow. The main result is: For two graphs G₁ and G₂ with δ ≥ 2 and G₂ not belonging to a well‐characterized class of graphs, the tensor product of G₁ and G₂ admits a nowhere‐zero 3‐flow. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 284–292, 2007     

Short cycle covers of graphs and nowhere‐zero flows

A shortest cycle cover of a graph G is a family of cycles which together cover all the edges of G and the sum of their lengths is minimum. In this article we present upper bounds to the length of shortest cycle covers, associated with the existence of two types of nowhere‐zero flows—circular flows and Fano flows. Fano flows, or Fano colorings, are nowhere‐zero ?‐flows on cubic graphs, with certain restrictions on the flow values meeting at a vertex. Such flows are conjectured to exist on every bridgless cubic graph. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 68:340‐348, 2011     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Nowhere‐zero 3‐flows in products of graphs

A graph G is an odd‐circuit tree if every block of G is an odd length circuit. It is proved in this paper that the product of every pair of graphs G and H admits a nowhere‐zero 3‐flow unless G is an odd‐circuit tree and H has a bridge. This theorem is a partial result to the Tutte's 3‐flow conjecture and generalizes a result by Imrich and Skrekovski [7] that the product of two bipartite graphs admits a nowhere‐zero 3‐flow. A byproduct of this theorem is that every bridgeless Cayley graph G = Cay(Γ,S) on an abelian group Γ with a minimal generating set S admits a nowhere‐zero 3‐flow except for odd prisms. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Nowhere zero flow and circuit covering in regular matroids

Let s(k) be the smallest s such that if there exists a k-nowhere zero flow in a regular matroid M, then M can be covered by circuits, the total length of which is at most s|M|. A recursive formula for the evaluation of s(k) is given: $\text{s(kt) ≤}\text{(s(k)(kt ? t) + s(t)(kt ? k))}\text{(kt ? 1)}$. By means of this formula s(k) is found for k = 2, 3, 4, 6, 7, 8. “Natural” proofs for graph theoretical results are obtained.     

Nowhere zero 4‐flow in regular matroids

Jensen and Toft 8 conjectured that every 2‐edge‐connected graph without a K₅‐minor has a nowhere zero 4‐flow. Walton and Welsh 19 proved that if a coloopless regular matroid M does not have a minor in {M(K_3,3), M*(K₅)}, then M admits a nowhere zero 4‐flow. In this note, we prove that if a coloopless regular matroid M does not have a minor in {M(K₅), M*(K₅)}, then M admits a nowhere zero 4‐flow. Our result implies the Jensen and Toft conjecture. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Multicommodity flows in graphs

Suppose that G is a graph, and (s_i,t_i) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between s_i and t_i and of value q_i, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s₁,…, s_l, t₁, …, t_l,…,t_l are all on the boundary of a face and s_l+1, …,S_k, t_l+1,…,t_k are all on the boundary of the infinite face or when t₁=?=t_l and G is planar and can be drawn so that s_l+1,…,s_k, t₁,…,t_k are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour.     

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].     

Multicommodity flows in cycle graphs

This paper considers the multicommodity flow problem and the integer multicommodity flow problem on cycle graphs. We present two linear time algorithms for solving each of the two problems.     

On dihedral flows in embedded graphs

Let be a multigraph with for each vertex a cyclic order of the edges incident with it. For , let be the dihedral group of order . Define . Goodall et al in 2016 asked whether admits a nowhere-identity -flow if and only if it admits a nowhere-identity -flow with (a “nowhere-identity dihedral -flow”). We give counterexamples to this statement and provide general obstructions. Furthermore, the complexity of deciding the existence of nowhere-identity -flows is discussed. Lastly, graphs in which the equivalence of the existence of flows as above is true are described. We focus particularly on cubic graphs.     

Nowhere-zero flows in low genus graphs

A nowhere-zero k-flow is an assignment of edge directions and integer weights in the range 1,…, k ? 1 to the edges of an undirected graph such that at every vertex the flow in is equal to the flow out. Tutte has conjectured that every bridgeless graph has a nowhere-zero 5-flow. We show that a counterexample to this conjecture, minimal in the class of graphs embedded in a surface of fixed genus, has no face-boundary of length <7. Moreover, in order to prove or disprove Tutte's conjecture for graphs of fixed genus γ, one has to check graphs of order at most 28(γ ? 1) in the orientable case and 14(γ ? 2) in the nonorientable case. So, in particular, it follows immediately that every bridgeless graph of orientable genus ?1 or nonorientable genus ?2 has a nowhere-zero 5-flow. Using a computer, we checked that all graphs of orientable genus ?2 or nonorientable genus ?4 have a nowhere-zero 5-flow.     

Location-domination in line graphs

A set $D$ of vertices of a graph $G$ is locating if every two distinct vertices outside $D$ have distinct neighbors in $D$; that is, for distinct vertices $u$ and $v$ outside $D$, $N\left(u\right)\cap D\ne N\left(v\right)\cap D$, where $N\left(u\right)$ denotes the open neighborhood of $u$. If $D$ is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of $G$. A graph $G$ is twin-free if every two distinct vertices of $G$ have distinct open and closed neighborhoods. It is conjectured (Garijo et al., 2014 [15]) and (Foucaud and Henning, 2016 [12]) respectively, that any twin-free graph $G$ without isolated vertices has a locating-dominating set of size at most one-half its order and a locating-total dominating set of size at most two-thirds its order. In this paper, we prove these two conjectures for the class of line graphs. Both bounds are tight for this class, in the sense that there are infinitely many connected line graphs for which equality holds in the bounds.     

Antisymmetric flows on planar graphs

We prove that every oriented planar graph admits a homomorphism to the Paley tournament P₂₇₁ and hence that every oriented planar graph has an antisymmetric flow number and a strong oriented chromatic number of at most 271. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 200–210, 2006     

Hamiltonian line graphs

Sufficient conditions on the degrees of a graph are given in order that its line graph have a hamiltonian cycle.     

Interval line graphs

We characterize the graphs whose line graphs are interval graphs.     

Generalized line graphs

Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation and construction of the 31 minimal nongeneralized line graphs, a Krausz-type covering characterization, and Whitney-type theorems on isomorphisms and automorphisms.     

The zero divisor graphs of Boolean posets

In this paper, it is proved that if B is a Boolean poset and S is a bounded pseudocomplemented poset such that S\Z(S) = {1}, then Γ(B) ≌ Γ(S) if and only if B ≌ S. Further, we characterize the graphs which can be realized as zero divisor graphs of Boolean posets.