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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.