I started wondering about the title question after seeing a talk by Kitty Meeks at FUN last summer that used this property, and found it again today in my notes from then. One answer is given by a simple and easy to count parameter of any graph, that is closely related to graph minors, maximum degree, bandwidth, and the number of connected subgraphs. Because I don't know what it might have been called before, I'll make up a name for it: the branch count.

To compute the branch count of a graph, perform the following steps. First, compute, for each vertex \( v, \) the excess of its degree over two: \( \max\{\operatorname{deg}(v)-2,0\}. \) Second, sum up these numbers within each connected component. Third, choose the largest number found in this way among all of the connected components.

This number is minor-monotone: contracting an edge between two vertices of degree two or more preserves it, because the increase by two (caused by subtracting two from a single merged vertex degree instead of separately from the degrees of two vertices) is offset by a decrease by two (caused by the removal of the two ends of the contracted edge). Other minor operations such as contracting a vertex with a degree-one endpoint or deleting an edge can only decrease the vertex degrees. Therefore, there are a finite number of minor-minimal graphs with a given branch count. In a minimal (simple) graph, every non-leaf edge must belong to a triangle, or else it could be contracted without changing the branch count. Using this fact, it is not hard to see that the unique minor minimal graph with branch count one is a claw \( K_{1,3}, \) while for branch count two there are three minimal graphs, the star \( K_{1,4}, \) the bull graph, and the diamond graph.

Minor-minimal graphs for branch count two

In a graph with branch count \( b, \) the largest star minor may be much smaller than \( b, \) of the form \( K_{1,O(b^{1/2})}; \) for instance, this is true for cliques, because their branch count is so much bigger than their number of vertices. On the other hand, every graph with branch count \( b \) has a star minor of the form \( K_{1,\Omega(b^{1/3})} \) that may be found as follows. First, contract all edges whose contraction does not change the branch count, to make the graph minimal. Second, if there is a vertex of degree \( b^{1/3}, \) return the star of it and its neighbors; otherwise, there are at least \( b^{2/3} \) vertices in the remaining graph. Third, do a breadth-first search. If one of the levels of the breadth first search has at least \( b^{1/3} \) vertices in it, form a star by contracting all the earlier levels and return it; otherwise, there are at least \( b^{1/3} \) levels. Finally, observe that (because of the triangle property) the last node in each level of the breadth first search must either have two or more neighbors on the next level of the BFS tree, or it must be a leaf of the BFS tree. Possibly by rearranging the tree (making the neighbors on the next level become the children of this last node) we can cause this node to either be an internal node with two or more children or a leaf in the tree. In this way, we get a tree in which the number of leaves plus the number of internal nodes with two or more children is at least \( b^{1/3}, \) and contracting the internal part of the tree gives us our desired star.

It turns out that, for a minor-closed family \( F, \) the following characterizations are all equivalent to each other

  1. \( F \) has bounded branch count.

  2. \( F \) has bounded maximum degree.

  3. \( F \) excludes at least one star \( K_{1,n} \).

  4. There is a polynomial bound on the number of connected subgraphs of graphs in \( F. \)

  5. \( F \) has bounded bandwidth.

Proof:

(1) ⇒ (2): If \( F \) has bounded branch count \( b, \) it can't have any single vertex of degree \( b+2 \) or greater.

(2) ⇒ (3): If \( F \) has maximum degree \( d, \) it excludes \( K_{1,d+1}. \)

(4) ⇒ (3): The star \( K_{1,n} \) has \( 2^n \) connected subgraphs, which is not polynomially bounded.

(1) ⇒ (4): If \( F \) has bounded branch count, its graphs have a bounded number of paths of degree-two vertices. Every connected subgraph has at most two cut edges on each such path, so the number of connected subgraphs is polynomial (with exponent at most twice the number of paths).

(3) ⇒ (1): This is the property of always having a star minor of size proportional to a function of the branch count, proved above.

(5) ⇒ (3): \( K_{1,n} \) has unbounded bandwidth, exactly \( \lceil n/2 \rceil. \)

(1) ⇒ (5): Sort the vertices by their distance from the set of vertices of degree three or more, breaking ties arbitrarily. There are \( O(b) \) vertices at each distance, so the bandwidth of this layout is \( O(b). \)

As a consequence, we have a polynomial time algorithm for solving any graph maximization problem on graphs of bounded branch count for which the solution is a connected subgraph, and for which the quality of a solution can be computed in polynomial time: just look at all connected subgraphs and pick the best one. For instance, the maximum weight planar subgraph fits this idea. Unfortunately this doesn't give fixed parameter tractability, because the exponent of the polynomial might depend on the branch count.

Unfortunately this also doesn't quite give a complete answer to the question about graphs with polynomially many connected subgraphs. For instance, the trees formed by a path of length \( n, \) together with \( \log n \) leaf edges attached somewhere along the path, also have this property. But they're not as nice from the point of view of graph minor theory...




Comments:

None:
2013-01-27T13:32:22Z
To add one characterization: I think having bounded max leaf number (see e.g. http://www.ii.uib.no/~daniello/papers/ecology1.pdf ) on the connected components gives the same class.
11011110:
2013-01-27T16:30:25Z
Yes, that's almost the same as having bounded star minors.