A contraction algorithm for finding small cycle cutsets

We consider the problem of finding a minimum size cutset in a directed graph G = (V, E), i.e., a vertex set that cuts all cycles in G. Since the general problem is NP-complete we concentrate on finding small cutsets. The algorithm we suggest uses contraction operations to reduce the graph size and to identify candidates for the cutset; the complexity of the algorithm is O(|E|log|V|). This contraction algorithm is compared to Shamir-Rosen algorithm. It is shown that the class of graphs for which the contraction algorithm finds a minimum cutset (completely contractible graphs) properly contains the class of graphs for which Shamir-Rosen algorithm finds a minimum cutset (quasi-reducible graphs) and thus that the contraction algorithm is more powerful. As a by-product of this analysis we construct a hierarchy of the classes of graphs for which minimum cutsets can be found efficiently. The class of quasi-reducible graphs lies, in this hierarchy, between two classes which are closely related. This result illuminates the nature of the quasi-reducible graphs. The hierarchy constructed allows us also to compare the Wang-Lloyd-Soffa algorithm to the Shamir-Rosen algorithm and to the contraction algorithm.     

Bipartite Subgraphs of Graphs with Maximum Degree Three

We prove that for a connected graph G with maximum degree 3 there exists a bipartite subgraph of G containing almost of the edges of G. Furthermore, we completely characterize the set of all extremal graphs, i.e. all connected graphs G=(V, E) with maximum degree 3 for which no bipartite subgraph has more than of the edges; |E| denotes the cardinality of E. For 2-edge-connected graphs there are two kinds of extremal graphs which realize the lower bound . Received: July 17, 1995 / Revised: April 5, 1996     

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     

Non-traceability of large connected claw-free graphs

Let G be a connected claw-free graph on n vertices. Let ς₃(G) be the minimum degree sum among triples of independent vertices in G. It is proved that if ς₃(G) ≥ n − 3 then G is traceable or else G is one of graphs G_n each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K₃. Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if ς₃(G) ≥ n − k, n > ν(k) and G is non-traceable, then G is a factor of a graph G_n. Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that ς₃(G) ≥ . This contrasts sharply with known results on NP-completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Overlap number of graphs

An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ(G) (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If δ(G)?2 and G≠K₃, then φ(G)?|E(G)| ? 1, with equality when G is connected and triangle‐free and has no star‐cutset. (3) If G is an n‐vertex plane graph with n?5, then φ(G)?2n ? 5, with equality when every face has length 4 and there is no star‐cutset. (4) If G is an n‐vertex graph with n?14, then φ(G)?n²/4 ? n/2 ? 1, with equality for even n when G arises from K_{n/2, n/2} by deleting a perfect matching. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Characterizing defect n-extendable graphs and -critical graphs

A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented.     

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

Equimatchable factor-critical graphs

A simple graph G(X, E) is factor-critical if the induced subgraph 〈X – x〉 admits a perfect matching for every vertex x of G. It is equimatchable if every maximal matching of G is maximum. The equimatchable non-factor-critical graphs have been studied by Lesk, Plummer, and Pulleyblank. In this paper, we study the equimatchable factor-critical graphs; in particular we show that if such a graph is two-connected, it is hamiltonian.     

The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

Let G be a graph of order n, maximum degree Δ, and minimum degree δ. Let P(G, λ) be the chromatic polynomial of G. It is known that the multiplicity of zero “0” of P(G, λ) is one if G is connected, and the multiplicity of zero “1” of P(G, λ) is one if G is 2‐connected. Is the multiplicity of zero “2” of P(G, λ) at most one if G is 3‐connected? In this article, we first construct an infinite family of 3‐connected graphs G such that the multiplicity of zero “2” of P(G, λ) is more than one, and then characterize 3‐connected graphs G with Δ + δ?n such that the multiplicity of zero “2” of P(G, λ) is at most one. In particular, we show that for a 3‐connected graph G, if Δ + δ?n and (Δ, δ₃)≠(n?3, 3), where δ₃ is the third minimum degree of G, then the multiplicity of zero “2” of P(G, λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

P4‐decompositions of regular graphs

In this article, we show that every simple r‐regular graph G admits a balanced P₄‐decomposition if r ≡ 0(mod 3) and G has no cut‐edge when r is odd. We also show that a connected 4‐regular graph G admits a P₄‐decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degree 4 that admit a triangle‐free Eulerian tour. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 135–143, 1999     

Double cycle covers and the petersen graph

Let O(G) denote the set of odd-degree vertices of a graph G. Let t ? N and let ??_t denote the family of graphs G whose edge set has a partition. E(g) = E₁ U E₂ U … U E_tsuch that O(G) = O(G[E_i]) (1 ? i ? t). This partition is associated with a double cycle cover of G. We show that if a graph G is at most 5 edges short of being 4-edge-connected, then exactly one of these holds: G ? ??₃, G has at least one cut-edge, or G is contractible to the Petersen graph. We also improve a sufficient condition of Jaeger for G ? ??_2p+1(p ? N).     

All hypoenergetic graphs with maximum degree at most 3

The energy E(G) of a graph G is defined as the sum of the absolute values of its eigenvalues. A connected graph G of order n is said to be hypoenergetic if E(G)<n. All connected hypoenergetic graphs with maximum degree Δ3 have been characterized. In addition to the four (earlier known) hypoenergetic trees, we now show that complete bipartite graph K_2,3 is the only hypoenergetic cycle-containing hypoenergetic graph. By this, the validity of a conjecture by Majstorović et al. has been confirmed.     

Exploring Unknown Undirected Graphs

A robot has to construct a complete map of an unknown environment modeled as an undirected connected graph. The task is to explore all nodes and edges of the graph using the minimum number of edge traversals. The penalty of an exploration algorithm running on a graph G = (V(G), E(G)) is the worst-case number of traversals in excess of the lower bound |E(G)| that it must perform in order to explore the entire graph. We give an exploration algorithm whose penalty is O(|V(G)|) for every graph. We also show that some natural exploration algorithms cannot achieve this efficiency.     

On feedback vertex sets and nonseparating independent sets in cubic graphs

Let G be an undirected connected graph with n nodes. A subset F of nodes of G is a feedback vertex set (fvs) if G ? F is a forest and a subset J of nodes of G is a nonseparating independent set (nsis) if no two nodes of J are adjacent and G ? J is connected. f(G), z(G) denote the cardinalities of a minimum fvs and a maximum nsis, respectively, of G. The equation f(G) = n/2 ? z(G) + 1 and two new upper bounds on f(G) are derived for cubic graphs G.     

Largest bipartite subgraphs in triangle-free graphs with maximum degree three

Let G be a triangle-free, loopless graph with maximum degree three. We display a polynomial algorithm which returns a bipartite subgraph of G containing at least ? of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3-regular, triangle-free, loopless, connected graphs for which no bipartite subgraph has more than this proportion.     

Partitioning planar graphs: a?fast combinatorial approach for max-cut

The max-cut problem asks for partitioning the nodes V of a graph G=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. (IEEE Trans. Comput. 39(5):694–697, 1990) and that of Berman et al. (WADS, Lecture Notes in Computer Science, vol. 1663, pp. 25–36, Springer, Berlin, 1999). The running time of the former can be bounded by O(|V|^\frac32log|V|)O(|V|^{\frac{3}{2}}\log|V|). The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the running time of O(|V|^\frac32(log|V|)^\frac32)a(|V|)O(|V|^{\frac{3}{2}}(\log|V|)^{\frac{3}{2}})\alpha(|V|), where α(|V|) is the inverse Ackermann function, it can solve large instances in practice.     

Unicycle graphs and uniquely restricted maximum matchings

A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. G is a unicycle graph if it owns only one cycle. Golumbic, Hirst and Lewenstein observed that for a tree or a graph with only odd cycles the size of a maximum uniquely restricted matching is equal to the matching number of the graph. In this paper we characterize unicycle graphs enjoying this equality. Moreover, we describe unicycle graphs with only uniquely restricted maximum matchings. Using these findings, we show that unicycle graphs having only uniquely restricted maximum matchings can be recognized in polynomial time.     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory