0
$\begingroup$

The block graph of a given graph $G$ is the intersection graph of its blocks. Thus, it has one vertex for each block of $G$, and an edge between two vertices whenever the corresponding two blocks share a vertex. A biconnected component (sometimes known as a 2-connected component or block) is a maximal biconnected subgraph. The blocks are attached to each other at shared vertices called cut vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components. I know that a graph block can be a $C_3$ such as the graph block of a $S_3$ (Star graph) also know as $K_{1,k}$ (Complete bipartite)

$\endgroup$
5
  • $\begingroup$ if the block graph had a cycle, the blocks that correspond to the nodes of that cycle would actually be one larger block (their intersections would not be articulation points). $\endgroup$ – JimN Apr 16 at 12:01
  • $\begingroup$ @JimN For that to work out, we need to define something slightly different from the block graph: a graph whose vertices correspond to blocks and cut vertices, with an edge from each cut vertex to the block it's in. In this definition, a cycle might happen from having many overlapping blocks. $\endgroup$ – Misha Lavrov Apr 16 at 13:38
  • $\begingroup$ And actually in this definition I think the statement is not true: doesn't an $n$-edge star graph have a block graph of $K_n$, which has many long cycles? $\endgroup$ – Misha Lavrov Apr 16 at 13:39
  • $\begingroup$ $C_n$-free means no induced $C_n$. The only induced cycles in $K_n$ are triangles $\endgroup$ – JimN Apr 16 at 13:40
  • $\begingroup$ Sorry, I already edited the title it wasn't that have a $C_n$ $n\geq 4$, but that it isn't a $C_n$ $n\geq 4$ $\endgroup$ – TMarengo Apr 22 at 0:45
0
$\begingroup$

Assume the block graph of $G$ has some cycle > 4. Choose an edge $xy$ in the cycle. Note that $x$ and $y$ are nodes that are connected by a path in the cycle which does not use edge $xy$.

So $x$ and $y$ each correspond to two blocks of $G$, which intersect, and their intersection should be an articulation point. Remove that vertex -- this should disconnect the graph, and in particular, disconnect a vertex in block $x$ from a vertex in block $y$. But now there is another path which connects the vertices of $x$ with the vertices of $y$ through the other path in the cycle.

This argument breaks down when the articulation point removed belongs to all blocks (as in your triangle case).

$\endgroup$

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.