The basic interpolation theorem states that if graph \(G\) contains spanning trees having \(m\) and \(n\) leaves, with \(m < n\), then for each integer \(k\) such that \(m < k < n\), \(G\) contains a spanning tree having \(k\) leaves. Various generalizations and related topics will be discussed.

We find the set of integers \(v\) for which \(\lambda K_v\) may be decomposed into sets of four triples forming Pasch configurations, for all \(\lambda\). We also remove the remaining exceptional values of \(v\) for decomposing \(K_v\) into sets of other four-triple configurations.

In this paper, we consider some combinatorial structures called balanced arrays (\(B\)-arrays) with a finite number of elements, and we derive some necessary conditions in the form of inequalities for the existence of these arrays. The results obtained here make use of the Holder Inequality.

We present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in \(O(n^{3})\) and \(O(n^2)\) time respectively. Our algorithm for computing the matching polynomial generalizes and improves the result in \([13]\) from \(O(n^3 \log n)\) time for trees and the chromatic polynomial algorithm improves the result in \([18]\) from \(O(n^4)\) time. The salient features of our results are the following:
Our techniques for computing the graph polynomials can be applied to certain other graph polynomials and other classes of graphs as well. Furthermore, our algorithms can also be parallelized into NC algorithms.

Given positive integers \(p\) and \(q\), a \((p, q)\)-colouring of a graph \(G\) is a mapping \(\theta: V(G) \rightarrow \{1, 2, \ldots, q\}\) such that \(\theta(u) \neq \theta(v)\) for all distinct vertices \(u, v\) in \(G\) whose distance \(d(u, v) \leq p\). The \(p\)th order chromatic number \(\chi^{(p)}(G)\) of \(G\) is the minimum value of \(q\) such that \(G\) admits a \((p, q)\)-colouring. \(G\) is said to be \((p, q)\)-maximally critical if \(\chi^{(p)}(G) = q\) and \(\chi^{(p)}(G + e) > q\) for each edge \(e\) not in \(G\).
In this paper, we study the structure of \((2, q)\)-maximally critical graphs. Some necessary or sufficient conditions for a graph to be \((2, q)\)-maximally critical are obtained. Let \(G\) be a \((2, q)\)-maximally critical graph with colour classes \(V_1, V_2, \ldots, V_q\). We show that if \(|V_1| = |V_2| = \cdots = |V_k| = 1\) and \(|V_{k+1}| = \cdots = |V_q| = h \geq 1\) for some \(k\), where \(1 \leq k \leq q-1\), then \(h \leq h^*\), where

\[h^* = \max \left\{k, \min\{q – 1, 2(q – 1 – k)\}\right\}.\]

Furthermore, for each \(h\) with \(1 \leq h \leq h^*\), we are able to construct a \((2, q)\)-maximally critical connected graph with colour classes \(V_1, V_2, \ldots, V_q\) such that \(|V_1| = |V_2| = \cdots = |V_k| = 1\) and \(|V_{k+1}| = \cdots = |V_q| = h\).