On block-related derived graphs

The cut vertex of a graph G is a vertex whose removal increases the number of components in the graph. A maximal connected subgraph with no cut vertex is called a block of the graph. This paper introduces and analyses the block-degree of a vertex and the cut-degree of a block. The block-degree of a vertex v is the number of blocks containing v. The cut-degree of a block b is the number of cut vertices of G contained in b. Given the block-degree sequence of cut vertices of a graph, the number of blocks of the graph and bounds on the order and size of the graph are studied. The block graph (B(G)) of a graph G is the graph whose vertices are blocks of G in which two vertices are adjacent whenever the corresponding blocks have a vertex in common. The number of cut vertices in B(G) is obtained and the graphs for which B(G) has exactly one cut vertex are characterized. Further, an investigation is carried out on the traversability of B(G). The block cut point graph BC(G) of a graph G is the graph whose vertices are the union of the set of blocks and the set of cut vertices of G and in which two vertices are adjacent if it corresponds to a block b of G and the other to a cut vertex c of G and c belongs to b in G. The properties of BC(G) and its iterations are studied. The graph G for which BC(G) is a perfect m-ary tree is characterised.