Minimum cycle coverings and integer flows

It was conjectured by Fan that if a graph G = (V,E) has a nowhere-zero 3-flow, then G can be covered by two even subgraphs of total size at most |V| + |E| - 3. This conjecture is proved in this paper. It is also proved in this paper that the optimum solution of the Chinese postman problem and the solution of minimum cycle covering problem are equivalent for any graph admitting a nowhere-zero 4-flow.     

3-connected graphs with non-cut contractible edge covers of size k

In this paper, we show that if a 3-connected graph G other than K₄ has a vertex subset K that covers the set of contractible edges of G and if |K| 3 and |V(G)| 3|K| ? 1, then K is a cutset of G. We also give examples to show that this result is best possible. In particular, the result does not hold for K with smaller cardinality.     

Smallest (1, 2)-eulerian weight and shortest cycle covering

The concept of a (1, 2)-eulerian weight was introduced and studied in several papers recently by Seymour, Alspach, Goddyn, and Zhang. In this paper, we proved that if G is a 2-connected simple graph of order n (n ≧ 7) and w is a smallest (1, 2)-eulerian weight of graph G, then |E_w=even | n - 4, except for a family of graphs. Consequently, if G admits a nowhere-zero 4-flow and is of order at least 7, except for a family of graphs, the total length of a shortest cycle covering is at most | V(G) | + |E(G) |- 4. This result generalizes some previous results due to Bermond, Jackson, Jaeger, and Zhang.     

An extremal problem for subdivisions of K

It is proved that every graph G with ‖G‖ ≥ 2|G| − 5, |G| ≥ 6, and girth at least 5, except the Petersen graph, contains a subdivision of K, the complete graph on five vertices minus one edge. © 1999 John Wiley & Sons, Inc, J. Graph Theory 30: 261–276, 1999     

Toughness and the existence of k-factors

A connected graph G is called t-tough if t · w(G - S) ? |S| for any subset S of V(G) with w(G - S) > 1, where w(G - S) is the number of connected components of G - S. We prove that every k-tough graph has a k-factor if k|G| is even and |G| ? k + 1. This result, first conjectured by Chvátal, is sharp in the following sense: For any positive integer k and for any positive real number ε, there exists a (k - ε)-tough graph G with k|G| even and |G| ? k + 1 which has no k-factor.     

Short cycle covers of cubic graphs

Let G be a bridgeless cubic graph. We prove that the edges of G can be covered by circuits whose total length is at most (44/27) |E(G)|, and if Tutte's 3-flow Conjecture is true, at most (92/57) |E(G)|.     

Independence number,connectivity, and r-factors

We show that if r ? 1 is an odd integer and G is a graph with |V(G)| even such that k(G) ? (r + 1)²/2 and (r + 1)²α(G) ? 4rk(G), then G has an r-factor; if r ? 2 is even and G is a graph with k(G) ? r(r + 2)/2 and (r + 2)α(G) ? 4k(G), then G has an r-factor (where k(G) and α(G) denote the connectivity and the independence number of G, respectively).     

Domination in graphs with minimum degree two

The domination number γ(G) of a graph G = (V, E) is the minimum cardinality of a subset of V such that every vertex is either in the set or is adjacent to some vertex in the set. We show that if a connected graph G has minimum degree two and is not one of seven exceptional graphs, then γ(G)γ 2/5|V|. We also characterize those connected graphs with γ(G)γ 2/5|V|.     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

Zero-Sum Flows in Regular Graphs

For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)²-flow. Finally, the existence of k-flows for small graphs is investigated.     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

Covering contractible edges in 3-connected graphs. II. Characterizing those with covers of size three

It is shown that if G is a 3-connected graph with |V(G)| ≥ 10, then, with the exception of one infinite class based on K_3,p, it takes at least four vertices to cover the set of contractible edges of G. © 1993 John Wiley & Sons, Inc.     

On component factors

LetK be a connected graph. A spanning subgraphF ofG is called aK-factor if every component ofF is isomorphic toK. On the existence ofK-factors we show the following theorem: LetG andK be connected graphs andp be an integer. Suppose|G| = n|K| and 1 <p < n. Also suppose every induced connected subgraph of orderp|K| has aK-factor. ThenG has aK-factor.     

Large centralizers in finite solvable groups

In 1955 R. Brauer and K. A. Fowler showed that ifG is a group of even order >2, and the order |Z(G)| of the center ofG is odd, then there exists a strongly real) elementx∈G−Z whose centralizer satisfies|C _G(x)|>|G|^1/3. In Theorem 1 we show that every non-abeliansolvable groupG contains an elementx∈G−Z such that|C _G(x)|>[G:G′∩Z]^1/2 (and thus|C _G(x)|>|G|^1/3). We also note that if non-abelianG is either metabelian, nilpotent or (more generally) supersolvable, or anA-group, or any Frobenius group, then|C _G(x)|>|G|^1/2 for somex∈G−Z. In Theorem 2 we prove that every non-abelian groupG of orderp ^mqⁿ (p, q primes) contains a proper centralizer of order >|G|^1/2. Finally, in Theorem 3 we show that theaverage |C(x)|, x∈G, is ≧c|G| ^1/3 for metabelian groups, wherec is constant and the exponent 1/3 is best possible.     

Hamiltonian graphs involving distances

Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G ?3K_n/3 U T₁ U T₂, where n ? O (mod 3), and T₁ and T₂ are the edge sets of two vertex disjoint triangles containing exactly one vertex from each K_n/3. This result generalizes both Fan's and Lindquester's results as well as several others.     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

On a Spanning Tree with Specified Leaves

Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. Dedicated to Professor Hikoe Enomoto on his 60th birthday.     

Edge-connectivity in p-partite graphs

Let G = (V, E) be a finite, simple p-partite graph with minimum degree δ and edge-connectivity γ. It is proved that if |V| ? (2pδ)/(p - 1) - 2 or in special cases that if |V| ? (2pδ)/(p - 1) - 1, then λ = δ. It is further shown that this result is best possible.     

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.     

Path factors of bipartite graphs

A path on n vertices is denoted by P_n. For any graph H, the number of isolated vertices of H is denoted by i(H). Let G be a graph. A spanning subgraph F of G is called a {P₃, P₄, P₅}-factor of G if every component of F is one of P₃, P₄, and P₅. In this paper, we prove that a bipartite graph G has a {P₃, P₄, P₅}-factor if and only if i(G ? S ? M) ≦ 2|S| + |M| for all S ? V(G) and independent M ? E(G).