Some special realizations of partition matrix sequences (Q1309467)

The notion of a partition matrix sequence of a graph is considered. Let \(G= (V,E)\) be a graph and let \(P= (V_ 1,\dots,V_ k)\) be an ordered partition of the set \(V\), where \(V_ i= (v_{i1},v_{i2},\dots, v_{is_ i})\), \(i= 1,\dots,k\). For every \(i\) \((1\leq i\leq k)\) there is a \((k\times s_ i)\)-matrix \(M_ i(G)= (a^ j_{i\ell})\), where \(a^ j_{i\ell}= | V_ j\cap\Gamma(v_{i\ell})|\), \(\ell= 1,\dots,s_ i\); \(j= 1,\dots,k\), and \(\Gamma(v_{i\ell})\) denotes the set of all neighbours of \(v_{i\ell}\) in \(G\). The sequence \(M_ P(G)= (M_ 1(G),\dots, M_ k(G))\) is called the \(P\)-matrix sequence of \(G\). In the paper \(P\)-matrix sequences of connected graphs, \(r\)-edge connected graphs and trees are characterized.