A typical vertex of a tree (Q1841915)

The paper studies a class of recursive algorithms for trees. Let \(a\), \(b\), \(c\) denote real numbers, let \(P_n\) denote the path on \(n\) vertices. A vertex of a tree is called typical, if it has at least two neighbors of degree 1 and 2. Let \(T^i_p\) denote the generic component after the removal of vertex \(p\) from the tree \(T\). Consider the following recursive algorithm to compute a real function \(f(T)\) of trees: initial conditions: \(f(P_1)= a\), \(f(P_2)= b\), recursion: \(f(T)= c+\sum_i f(T^i_p)\), where \(p\) is a typical vertex of \(T\). The paper shows that \(f(T)\) is a well-defined function if and only if \(3a- 2b+ c=0\). This algorithm has two interesting special cases, one is Nylen's algorithm (see \textit{P. M. Nylen} [Linear Algebra Appl. 248, 303-316 (1996; Zbl 0864.05069)]) to compute the minimum rank \(m(T)\) of symmetric matrices whose entries are nonzero if and only if the corresponding entries of the adjacency matrix of \(T\) are nonzero; the other is computing the separating number \(s(T)\) of the tree, where \(s(T)= \max\{c_T(U)-|U|: U\subseteq V(T)\}\), and \(c_T(U)\) denotes the number of components of \(T\) after the removal of the vertex set \(U\). Finally, it is shown that all \(f(T)\) solutions of the recurrence can be written as \({a+ c\over 2}|V(T)|+ {a-c\over 2} s(T)\), and that \(m(T)=|V(T)|- s(T)\). The latter observation is due to \textit{C. R. Johnson} and \textit{A. L. Duarte} [Linear Multilinear Algebra 46, No. 1-2, 139-144 (1999; Zbl 0929.15005)].