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     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.     

Minimally (k,k)‐edge‐connected graphs

For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

A characterization of weakly four‐connected graphs

A graph G = (V, E) is called weakly four‐connected if G is 4‐edge‐connected and G ? x is 2‐edge‐connected for all x ∈ V. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using these results we prove that every minimally weakly four‐connected graph on at least four vertices contains at least three ‘splittable’ vertices of degree four, which gives rise to an inductive construction of weakly four‐connected graphs. Our results can also be applied in the problem of finding 2‐connected orientations of graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 217–229, 2006     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

Spanning 2‐trails from degree sum conditions

Suppose G is a simple connected n‐vertex graph. Let σ₃(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ₃G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K_1,3. Second, if σ₃(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ₃(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K_2,3 or K (the 6‐vertex graph obtained from K_2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

Sufficient conditions for graphs to be λ′‐optimal,super‐edge‐connected,and maximally edge‐connected

The restricted‐edge‐connectivity of a graph G, denoted by λ′(G), is defined as the minimum cardinality over all edge‐cuts S of G, where G‐S contains no isolated vertices. The graph G is called λ′‐optimal, if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G. A graph is super‐edge‐connected, if every minimum edge‐cut consists of edges adjacent to a vertex of minimum degree. In this paper, we present sufficient conditions for arbitrary, triangle‐free, and bipartite graphs to be λ′‐optimal, as well as conditions depending on the clique number. These conditions imply super‐edge‐connectivity, if δ (G) ≥ 3, and the equality of edge‐connectivity and minimum degree. Different examples will show that these conditions are best possible and independent of other results in this area. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 228–246, 2005     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

Connectivity keeping trees in k‐connected graphs

We show that one can choose the minimum degree of a k‐connected graph G large enough (independent of the vertex number of G) such that G contains a copy T of a prescribed tree with the property that G ? V(T) remains k‐connected. This was conjectured in [W. Mader, J Graph Theory 65 (2010), 61–69]. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 324–329, 2012     

Circuits through prescribed vertices in k‐connected k‐regular graphs

We show that every set of vertices in a k‐connected k‐regular graph belongs to some circuit. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 145–163, 2002     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

Codiameters of 3‐connected 3‐domination critical graphs

A graph G is 3‐domination critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Let G be a 3‐connected 3‐domination critical graph of order n. In this paper, we show that there is a path of length at least n?2 between any two distinct vertices in G and the lower bound is sharp. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 76–85, 2002     

Hamiltonian N2‐locally connected claw‐free graphs

A graph G is N₂‐locally connected if for every vertex ν in G, the edges not incident with ν but having at least one end adjacent to ν in G induce a connected graph. In 1990, Ryjá?ek conjectured that every 3‐connected N₂‐locally connected claw‐free graph is Hamiltonian. This conjecture is proved in this note. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 142–146, 2005     

Long paths through four vertices in a 2‐connected graph

Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000     

3‐Flows and Combs

Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected.     

Relative length of longest paths and cycles in 3‐connected graphs

For a graph G, let p(G) denote the order of a longest path in G and c(G) the order of a longest cycle in G, respectively. We show that if G is a 3‐connected graph of order n such that for every independent set {x₁, x₂, x₃, x₄}, then G satisfies c(G) ≥ p(G) ? 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001     

Vertex‐disjoint cycles containing prescribed vertices

Enomoto 7 conjectured that if the minimum degree of a graph G of order n ≥ 4k ? 1 is at least the integer , then for any k vertices, G contains k vertex‐disjoint cycles each of which contains one of the k specified vertices. We confirm the conjecture for n ≥ ck² where c is a constant. Furthermore, we show that under the same condition the cycles can be chosen so that each has length at most six. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 276–296, 2003