0
$\begingroup$

For a graph $G$ on $n \geq 1$ vertices, what is the maximum number of vertices of its block-cutpoint graph $BC(G)$?

What I have so far:

The block-cutpoint graph of a graph $G$ is the bipartite graph which consists of the set of cut-vertices of $G$ and a set of vertices which represent the blocks of $G$.

Let $G=(V,E)$ be a connected graph. Let $v$ be a vertex of $G$. Then $v$ is a cut-vertex of $G$ iff the vertex deletion $G−v$ is a vertex cut of $G$.That is, such that $G−v$ is disconnected.

A block is a maximal biconnected subgraph of a given graph $G$.

I don't really know what else I need to know to solve this.

$\endgroup$
1
$\begingroup$

It’s sufficient to consider connected graphs. First note that $G$ has at least $2$ non-cut vertices and therefore at most $n-2$ cut vertices. Next, let $\mathscr{B}$ be the set blocks of $G$. Let $\operatorname{bt}(G)$ be the graph whose vertex set is $\mathscr{B}$ and that has an edge $B_0B_1$ if and only if blocks $B_0$ and $B_1$ have a vertex in common.

  • Show that distinct $B_0,B_1\in\mathscr{B}$ have at most one vertex in common, and that if they have one in common, it’s a cut vertex. Show further that $\operatorname{bt}(C)$ is a tree. (It’s the block tree of $G$.)

  • Show that $|\mathscr{B}|\le n-1$. I used the fact that $\operatorname{bt}(G)$ is a tree to do this, which is why I introduced the block tree, but if you can find some other way to do it, that’s fine too.

It follows that $BC(G)$ has at most $2n-3$ vertices. To prove that this bound is sharp, consider the path graph with $n$ vertices.

Added: This of course applies only to the non-degenerate case $n>1$. If $n=1$, $G$ has no biconnected subgraph and no cut vertex.

$\endgroup$
3
  • $\begingroup$ Sorry this is a late reply. Why does G have at least 2 non-cut vertices? What do you mean when you say "this bound is sharp"? $\endgroup$
    – EmaLee
    Apr 24 '15 at 20:01
  • 1
    $\begingroup$ @EmaLee: The link in my answer is to a proof that $G$ has at least two non-cut vertices, and that page has a further link to a page with more proofs. When we say that a bound is sharp, we mean that it cannot be improved; in this case that means that there is at least one graph on $n$ vertices whose block-cut graph has $2n-3$ vertices, so $2n-3$ cannot be replaced by any smaller function of $n$. $\endgroup$ Apr 24 '15 at 20:04
  • $\begingroup$ This is false when $n=1$. $\endgroup$ Jun 3 '15 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.