Degree sum and nowhere-zero 3-flows

Let G be a simple graph on n vertices. In this paper, we prove that if G satisfies the condition that d(x)+d(y)≥n for each xy∈E(G), then G has no nowhere-zero 3-flow if and only if G is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices.     

Pósa-condition and nowhere-zero 3-flows

Let G be a simple graph on n vertices and π(G)=(d₁,d₂,…,d_n) be the degree sequence of G, where n≥3 and d₁≤d₂≤?≤d_n. The classical Pósa’s theorem states that if d_m≥m+1 for and d_m+1≥m+1 for n being odd and , then G is Hamiltonian, which implies that G admits a nowhere-zero 4-flow. In this paper, we further show that if G satisfies the Pósa-condition that d_m≥m+1 for and d_m+1≥m+1 for n being odd and , then G has no nowhere-zero 3-flow if and only if G is one of seven completely described graphs.     

Cycle covers of graphs with a nowhere-zero 4-flow

It is shown that the edges of a simple graph with a nowhere-zero 4-flow can be covered with cycles such that the sum of the lengths of the cycles is at most |E(G)| + |V(G)| ?3. This solves a conjecture proposed by G. Fan.     

On zero-sum -flows of graphs

For a graph G, a zero-sum flow is an assignment of non-zero real numbers on the edges of G such that the total sum of all edges incident with any vertex of G is zero. A zero-sum k-flow for a graph G is a zero-sum flow with labels from the set {±1,…,±(k-1)}. In this paper for a graph G, a necessary and sufficient condition for the existence of zero-sum flow is given. We conjecture that if G is a graph with a zero-sum flow, then G has a zero-sum 6-flow. It is shown that the conjecture is true for 2-edge connected bipartite graphs, and every r-regular graph with r even, r>2, or r=3.     

Nowhere-zero 3-flows of highly connected graphs

Let G be a k-edge-connected graph of order n. If k4log₂ n then G has a nowhere-zero 3-flow.     

Join of two graphs admits a nowhere-zero 3-flow

Let G be a graph, and λ the smallest integer for which G has a nowherezero λ-flow, i.e., an integer λ for which G admits a nowhere-zero λ-flow, but it does not admit a (λ ? 1)-flow. We denote the minimum flow number of G by Λ(G). In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ(G ∨ H) ? 3 except two cases: (i) One of the graphs G and H is K ₂ and the other is 1-regular. (ii) H = K ₁ and G is a graph with at least one isolated vertex or a component whose every block is an odd cycle. Among other results, we prove that for every two graphs G and H with at least 4 vertices, Λ(G ∨ H) ? 3.     

Distance-regular graphs without 4-claws

We determine the distance-regular graphs with diameter at least 3 and $c_2\ge 2$ but without induced $K_{1,4}$-subgraphs.     

New families of graphs without short cycles and large size

We denote by ex(n;{C₃,C₄,…,C_s}) or f_s(n) the maximum number of edges in a graph of order n and girth at least s+1. First we give a method to transform an n-vertex graph of girth g into a graph of girth at least g−1 on fewer vertices. For an infinite sequence of values of n and s∈{4,6,10} the obtained graphs are denser than the known constructions of graphs of the same girth s+1. We also give another different construction of dense graphs for an infinite sequence of values of n and s∈{7,11}. These two methods improve the known lower bounds on f_s(n) for s∈{4,6,7,10,11} which were obtained using different algorithms. Finally, to know how good are our results, we have proved that for s∈{5,7,11}, and for s∈{6,10}.     

The size of strength-maximal graphs

Let G be a graph and let k′(G) be the edge-connectivity of G. The strength of G, denoted by k?′(G), is the maximum value of k′(H), where H runs over all subgraphs of G. A simple graph G is called k-maximal if k?′(G) ≤ k but for any edge e ∈ E(G^c), k?′(G + e) ≥ k + 1. Let G be a k-maximal graph of order n. In [3], Mader proved |E(G)| ≤ (n - k)k + (). In this note, we shall show (n - 1)k - () In?n/k + 2)? ≤ |E(G|, and characterize the extremal graphs. We shall also give a characterization of all k-maximal graphs.     

Note on Integer 4-flows in Graphs

Acta Mathematica Sinica, English Series - Let G be a bridgeless graph and C be a circuit in G. To find a shorter circuit cover of G, Fan proposed a conjecture that if G/C admits a nowhere-zero...     

Nowhere-zero 3-flows in Cayley graphs and Sylow 2-subgroups

Tutte’s 3-Flow Conjecture suggests that every bridgeless graph with no 3-edge-cut can have its edges directed and labelled by the numbers 1 or 2 in such a way that at each vertex the sum of incoming values equals the sum of outgoing values. In this paper we show that Tutte’s 3-Flow Conjecture is true for Cayley graphs of groups whose Sylow 2-subgroup is a direct factor of the group; in particular, it is true for Cayley graphs of nilpotent groups. This improves a recent result of Potočnik et al. (Discrete Math. 297:119–127, 2005) concerning nowhere-zero 3-flows in abelian Cayley graphs.     

The maximum size of hypergraphs without generalized 4-cycles

Let fr(n) be the maximum number of edges in an r-uniform hypergraph on n vertices that does not contain four distinct edges A, B, C, D with A∪B=C∪D and A∩B=C∩D=∅. This problem was stated by Erd?s [P. Erd?s, Problems and results in combinatorial analysis, Congr. Numer. 19 (1977) 3-12]. It can be viewed as a generalization of the Turán problem for the 4-cycle to hypergraphs.Let . Füredi [Z. Füredi, Hypergraphs in which all disjoint pairs have distinct unions, Combinatorica 4 (1984) 161-168] observed that ?r?1 and conjectured that this is equality for every r?3. The best known upper bound ?r?3 was proved by Mubayi and Verstraëte [D. Mubayi, J. Verstraëte, A hypergraph extension of the bipartite Turán problem, J. Combin. Theory Ser. A 106 (2004) 237-253]. Here we improve this bound. Namely, we show that for every r?3, and ?₃?13/9. In particular, it follows that ?r→1 as r→∞.     

The rank and size of graphs

We show that the number of points with pairwise different sets of neighbors in a graph is O(2^r/2), where r is the rank of the adjacency matrix. We also give an example that achieves this bound. © 1996 John Wiley & Sons, Inc.