Forcing highly connected subgraphs

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007     

Highly connected monochromatic subgraphs

We conjecture that for n>4(k-1) every 2-coloring of the edges of the complete graph K_n contains a k-connected monochromatic subgraph with at least n-2(k-1) vertices. This conjecture, if true, is best possible. Here we prove it for k=2, and show how to reduce it to the case n<7k-6. We prove the following result as well: for n>16k every 2-colored K_n contains a k-connected monochromatic subgraph with at least n-12k vertices.     

Finding 2-edge connected spanning subgraphs

This paper studies the NP-hard problem of finding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G=(V,E) finds a 2-ECSS of size at most |V|+(|E|−|V|)/(r−1). For r-regular, r-edge connected input graphs for r=3, 4, 5 and 6, this gives approximation guarantees of and , respectively.     

Generating 3-vertex connected spanning subgraphs

In this paper we present an algorithm to generate all minimal 3-vertex connected spanning subgraphs of an undirected graph with n vertices and m edges in incremental polynomial time, i.e., for every K we can generate K (or all) minimal 3-vertex connected spanning subgraphs of a given graph in O(K²log(K)m²+K²m³) time, where n and m are the number of vertices and edges of the input graph, respectively. This is an improvement over what was previously available and is the same as the best known running time for generating 2-vertex connected spanning subgraphs. Our result is obtained by applying the decomposition theory of 2-vertex connected graphs to the graphs obtained from minimal 3-vertex connected graphs by removing a single edge.     

A characterization of well-covered graphs in terms of prohibited costable subgraphs

A graph is calledwell-covered if all maximal independent subsets in it have the same number of elements. LetI be an independent subset (possibly empty) in a graphG. The subgraph ofG obtained by erasing the setI together with its neighborhood is calledcostable. We present a characterization of the class of well-covered graphs in terms of the minimal set of prohibited costable subgraphs. This characterization implies characterizations of some well-known subclasses of the class of well-covered graphs as well as the existence of a polynomial algorithm for the recognition of well-covered graphs with bounded valences. Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 52–56, January, 2000.     

Edge cover by connected bipartite subgraphs

We consider the problem of covering the edge set of an unweighted, undirected graph with the minimum number of connected bipartite subgraphs (where the subgraphs are not necessarily bicliques). We show that this is an NP-hard problem, provide lower bounds through an integer programming formulation, propose several constructive heuristics and a local search, and discuss computational results. Finally, we consider a constrained variant of the problem which we show to be NP-hard, and provide an integer programming formulation for the variant.     

Two-edge connected spanning subgraphs and polyhedra

This paper studies the problem of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. We discuss the polytope associated with the solutions to this problem. We show that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. We also give some classes of facet defining inequalities of this polytope when the graph is general.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and CP Rail and the German Research Association (Deutsche Forschungsgemeinschaft SFR 303).     

Highly connected multicoloured subgraphs of multicoloured graphs

Suppose the edges of the complete graph on n vertices, E(K_n), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4, that if r=2s+1 then the answer lies between and , and that phase transitions occur at s=r/2 and . We shall also mention some of the more glaring open problems relating to this question.     

On the number of unique subgraphs

Entringer and Erdös introduced the concept of a unique subgraph of a given graph G and obtained a lower bound for the maximum number of unique subgraphs in any n-point graph, which we now improve.     

Contractible subgraphs in k‐connected graphs

For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007     

Partitioning a graph into monochromatic connected subgraphs

We show that every -edge-colored graph on vertices with minimum degree at least can be partitioned into two monochromatic connected subgraphs, provided is sufficiently large. This minimum degree condition is tight and the result proves a conjecture of Bal and DeBiasio. We also make progress on another conjecture of Bal and DeBiasio on covering graphs with large minimum degree with monochromatic components of distinct colors.     

On the number of connected convex subgraphs of a connected acyclic digraph

A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Non-separating trees in connected graphs

Let T be any tree of order d≥1. We prove that every connected graph G with minimum degree d contains a subtree T^′ isomorphic to T such that G−V(T^′) is connected.     

Highly connected coloured subgraphs via the regularity lemma

For integers , n≥k and r≥s, let m(n,r,s,k) be the largest (in order) k-connected component with at most s colours one can find in any r-colouring of the edges of the complete graph K_n on n vertices. Bollobás asked for the determination of m(n,r,s,k).Here, bounds are obtained in the cases s=1,2 and k=o(n), which extend results of Liu, Morris and Prince. Our techniques use Szemerédi’s Regularity Lemma for many colours.We shall also study a similar question for bipartite graphs.     

On the complexity of partitioning graphs into connected subgraphs

This paper is mainly concerned with the computational complexity of determining whether or not the vertices of a graph can be partitioned into equal sized subsets so that each subset induces a particular type of graph. Many of the NP-completeness results are for planar graphs. These are proved using a planar version of 3-dimensional matching.