In a graph $G$, a block is a maximal subgraph which has no cut-vertex or articulation vertex. For example in the given figure there are four blocks; these are induced subgraphs on vertex sets $B_1=\{v_1,v_2,v_3\},\ B_2=\{v_3,v_4\},\ B_3=\{v_3,v_6,v_5, v_7\}, \ B_4=\{v_7,v_8,v_9\}$.

Let graph $G$ has $n$ vertices, and there are $k$ number of blocks $B_1, B_2, \dots, B_k$ having $n_1,n_2,\dots n_k$ number of vertices, respectively. Then, the following relation holds $$n=\sum_{i=1}^{k}(n_i-1)+1.$$ Now, I have following two questions.

  1. Let the blocks $B_1, B_2, \dots, B_k$ have $t_1, t_2, \dots, t_k$ number of cut-vertices of $G$, respectively. Then what can be a relation between $n, ~ n_i$, and $t_i$.

  2. For which combinations of $n_i$, and $t_i$ the following inequality is true. $$\sum_{i=1}^{k}2^{t_i}(n_i-t_i)^{2.81}< n^{2.81}.$$

Solution of any of above two problems is welcome. enter image description here

  • 1
    $\begingroup$ Blocks and cut vertices form a tree $T$ (where an edge betwee a block $B$ and a cut vertex $x$ corresponds to $x\in B$). So, $t_1,\dots,t_k$ are degrees of blocks in this tree. A necessary property of $T$ is that all terminal vertices are blocks. If this property is satisfies and also $n_i\geqslant t_i$, we may construct a graph with these parameters (blocks $B_i$ may be taken complete graphs on corresponding $t_i$ cut vertices and additional $n_i-t_i$ vertices.) So, the question is: what are possible white degree sequences in a white-black tree, in which all terminal vertices are white $\endgroup$ – Fedor Petrov Mar 27 '17 at 12:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.