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)
$\begingroup$
$\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$– JimNApr 16, 2021 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 LavrovApr 16, 2021 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 LavrovApr 16, 2021 at 13:39
-
$\begingroup$ $C_n$-free means no induced $C_n$. The only induced cycles in $K_n$ are triangles $\endgroup$– JimNApr 16, 2021 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$– TMarengoApr 22, 2021 at 0:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
