Let \((G,C)\) be an edge-colored bipartite graph with bi-partition \((X,Y)\). A heterochromatic matching of \(G\) is such a matching in which no two edges have the same color. Let \(N^c(S)\) denote a maximum color neighborhood of \(S \subseteq V(G)\).

The spanning tree packing number of a connected graph \(G\), denoted by \(\tau(G)\), is the maximum number of edge-disjoint spanning trees of \(G\). In this paper, we determine the minimum number of edges that must be added to \(G\) so that the resulting graph has spanning tree packing number at least \(k\), for a given value of \(k\).

Let \(\gamma_{\overline{E}}\) and \(\gamma_{\overline{S}}\) be the minus edge domination and minus star domination numbers of a graph, respectively, and let \(\gamma_E\), \(\beta_1\), \(\alpha_1\) be the edge domination, matching, and edge covering numbers of a graph. In this paper, we present some bounds on \(\gamma_{\overline{E}}\) and \(\gamma_{\overline{S}}\) and characterize the extremal graphs of even order \(n\) attaining the upper bound \(\frac{n}{2}\) on \(\gamma_{\overline{E}}\). We also investigate the relationships between the above parameters.

The Wiener index of a connected graph is defined as the sum of all distances between unordered pairs of vertices. We determine the unicyclic graphs of given order, cycle length and number of pendent vertices with minimum Wiener index.

In this paper, by using the generating functions of Fibonacci polynomial sequences and their partial derivatives, we work out some identities involving the Fibonacci polynomials. As their primary applications, we obtain several identities involving the Fibonacci numbers and Lucas numbers.

Fukuda and Handa \([7]\) asked whether every even partial cube \(G\) is harmonic-even. It is shown that the answer is positive if the isometric dimension of \(G\) equals its diameter which is in turn true for partial cubes with isometric dimension at most \(6\). Under an additional technical condition it is proved that an even partial cube \(G\) is harmonic-even or has two adjacent vertices whose diametrical vertices are at distance at least \(4\). Some related open problems are posed.

By means of partial fraction decomposition, the purpose of this paper is to obtain a generalization of an algebraic identity which was given by Chu in \(\textit{The Electronic J. Camb.}\), \(11(2004), \#N15\).

Let \(G\) be a graph on \(n\) vertices \(v_1, v_2, \ldots, v_n\) and let \(d(v_i)\) be the degree of the vertex \(v_i\). If \((d(v_1), d(v_2), \ldots, d(v_n))^t\) is an eigenvector of the \((0,1)\)-adjacency matrix of \(G\), then \(G\) is said to be harmonic. A semi-regular harmonic graph is the harmonic graph which has exactly two different degrees. An equi-bipartite harmonic graph is the bipartite graph \(H = (X, Y; E)\) with \(|X| = |Y|\). In this paper, we characterize the semi-regular harmonic graph and equi-bipartite harmonic graph, and the degree sequence of equi-bipartite \(3\)-harmonic graphs.

We give necessary and sufficient conditions for a resolvable \(4\)-decomposition of \(AK_n\), in the case where \(H\) is one of the 10 graphs obtained by the union of two paths of length 2, with two possible exceptions. In particular, we complete the \(4\)-star (\(\lambda\)) and \(T\) (\(\tau\)) for higher \(\lambda\) and give complete solutions for resolvable decompositions into Fish (\(4\)-\(3\)), Mulinetto (\(hx\)) and Kites (\(BSI\)). In the cases of the Fish and Mulinetto the solution is obtained \(1\)-rotationally.

We note that with only a slight modification, Su’s proof on the fragments in \(k\)-critical \(n\)-connected graphs (see J. Graph Theory \(45 (2004), 281-297\)) can imply the following more general result: every non-complete \(W\)-locally \(k\)-critical \(n\)-connected graph has \(2k + 2\) distinct fragments \(F_1, F_2, \ldots, F_{2k+2}\) such that \(F_1 \cap W, F_2 \cap W, \ldots, F_{2k+2} \cap W\) are pairwise disjoint.