A vertex\(|\)matching-partition \((V|M)\) of a simple graph \(G\) is a spanning collection of vertices and independent edges of \(G\). Let vertex \(v \in V\) have weight \(w_v\) and edge \(e \in M\) have weight \(w_e\). Then the weight of \(V|M\) is \(w(V|M) = \prod_{v \in V} w_v + \prod_{e \in M} w_e\). Define the vertex|matching-partition function of \(G\) as \(W(G) = \sum_{V|M} w(V|M)\).

In this paper, we study this function when \(G\) is a path and a cycle. We generate all orthogonal polynomials as vertex|matching-partition functions of suitably labelled paths, and indicate how to find their derivatives in some cases. Here Taylor’s Expansion is used, and an application to associated polynomials is given. We also give a combinatorial interpretation of coefficients in the case of multiplicative and additive weights. Results are extended to the weighted cycle.

Let \(k\) be a nonnegative integer, and let \(\gamma(G)\) and \(i(G)\) denote the domination number and the independent domination number of a graph \(G\), respectively. The so-called \(i_k\)-perfect graphs consist of all such graphs \(G\) in which \(i(H) – \gamma(H) \leq k\) holds for every induced subgraph \(H\) of \(G\). This concept, introduced by I. Zverovich in \([5]\), generalizes the well-known domination perfect graphs. He conjectured that \(i\gamma (k)\)-perfect graphs also have a finite forbidden induced subgraphs characterization, as is the case for domination perfect graphs. Recently, Dohmen, Rautenbach, and Volkmann obtained such a characterization for all \(i\gamma(1)\)-perfect forests. In this paper, we characterize the \(i\gamma(1)\)-perfect graphs with girth at least six.

Let \(G\) be a simple and connected graph of order \(p \geq 2\). A \({proper k-total-coloring}\) of a graph \(G\) is a mapping \(f\) from \(V(G) \bigcup E(G)\) into \(\{1, 2, \ldots, k\}\) such that every two adjacent or incident elements of \(V(G) \bigcup E(G)\) are assigned different colors. Let \(C_f(u) = f(u) \bigcup \{f(uv) | uv \in E(G)\}\) be the \({neighbor \;color-set}\) of \(u\). If \(C_f(u) \neq C_f(v)\) for any two vertices \(u\) and \(v\) of \(V(G)\), we say \(f\) is a \({vertex-distinguishing \;proper\; k-total-coloring}\) of \(G\), or a \({k-VDT-coloring}\) of \(G\) for short. The minimal number of all \(k\)-VDT-colorings of \(G\) is denoted by \(\chi_{vt}(G)\), and it is called the \({VDTC \;chromatic \;number}\) of \(G\). For some special families of graphs, such as the complete graph \(K_n\), complete bipartite graph \(K_{m,n}\), path \(P_m\), and circle \(C_m\), etc., we determine their VDTC chromatic numbers and propose a conjecture in this article.

The cochromatic number of a graph \(G\), denoted by \(z(G)\), is the fewest number of parts we need to partition \(V(G)\) so that each part induces in \(G\) an empty or a complete graph. A graph \(G\) with \(z(G) = n\) is called \({critically n-cochromatic}\) if \(z(G – v) = n – 1\) for each vertex \(v\) of \(G\), and \({minimally n-cochromatic}\) if \(z(G – e) = n – 1\) for each edge \(e\) of \(G\).

We show that for a graph \(G\), \(K_{1} \cup G \cup K_{2} \cup \cdots \cup K_{n-1} \cup G\) is a critically \(n\)-cochromatic graph if and only if \(G\) is \(K_{n}\), \((n \geq 2)\). We consider general minimally cochromatic graphs and obtain a result that a minimally cochromatic graph is either a critically cochromatic graph or a critically cochromatic graph plus some isolated vertices. We also prove that given a graph \(G\), then \(K_{1} \cup G \cup K_{2} \cup \cdots \cup K_{n-1} \cup G\) \((n \geq 2)\) is minimally \(n\)-cochromatic if and only if \(G\) is \(K_{n}\) or \(\overline{K_{n-1}} \cup \overline{K_{p}}\) for \(p \geq 1\). We close by giving some properties of minimally \(n\)-cochromatic graphs.

We examine the inverse domination number of a graph, as well as two reasonable candidates for the fractional analogue of this parameter. We also examine the relations among these and other graph parameters. In particular, we show that both proposed fractional analogues of the inverse domination number are no greater than the fractional independence number. These results establish the fractional analogue of a well-known conjecture about the inverse domination and vertex independence numbers of a graph.

We consider a \(2\)-coloring of arcs on the primitive extremal tournament with the largest exponent on \(n\) vertices and \(m\) arcs. This \(2\)-colored digraph is a \(2\)-primitive tournament. Then we consider the \(2\)-exponent of a \(2\)-primitive tournament. In this paper, we give an upper bound for the \(2\)-exponent of the primitive extremal tournament.

Let \(G = (V(G), E(G))\) be a nonempty graph (may have parallel edges). The line graph \(L(G)\) of \(G\) is the graph with \(V(L(G)) = E(G)\), and in which two vertices \(e\) and \(e’\) are joined by an edge if and only if they have a common vertex in \(G\). We call the complement of \(L(G)\) as the jump graph. In this note, we give a simple sufficient and necessary condition for a jump graph to have a perfect matching.

We introduce a new technique for constructing pairwise balanced designs and group divisible designs from finite groups. These constructed designs do not yield designs with new parameters, but our construction gives rise to designs having a transitive automorphism group that also preserves the resolution classes.

A shell graph of order \(n\), denoted by \(H(n, n-3)\), is the graph obtained from the cycle \(C_n\) of order \(n\) by adding \(n-3\) chords incident with a common vertex, say \(u\). Let \(v\) be a vertex adjacent to \(u\) in \(C_n\). Sethuraman and Selvaraju \([3]\) conjectured that for all \(k \geq 1\) and for all \(n_i \geq 4\), \(1 \leq i \leq k\), one edge \((uv)\) union of \(k\)-shell graphs \(H(n_i, n_i – 3)\) is cordial. In this paper, we settle this conjecture affirmatively.

In this paper, we give formulas for the sums of generalized order-\(k\) Fibonacci, Pell, and similar other sequences, which we obtain using matrix methods. As applications, we give explicit formulas for the Tribonacci and Tetranacci numbers.