In this paper, we give a sufficient and necessary condition for a \(k\)-extendable graph to be \(2k\)-factor-critical when \(k = \frac{v}{4}\), and prove some results on independence numbers in \(n\)-factor-critical graphs and \(k\frac{1}{2}\)-extendable graphs.

In this paper, we show that some families of graphs are arbitrarily graceful or almost graceful.

We consider the lattice of order ideals of the union of an \(n\)-element fence and an antichain of size \(i\), whose Hasse diagram turns out to be isomorphic to the \(i\)-th extended Fibonacci cube. We prove that the Whitney numbers of these lattices form a unimodal sequence satisfying a particular property, called \({alternating}\), we find the maximum level of the game sequence and determine the exact values of these numbers.

Let \(D\) be a strongly connected digraph with order at least two. Let \(T(D)\) denote the total digraph of \(D\), and let \(\kappa(D)\) and \(\lambda(D)\) denote the connectivity and arc-connectivity of \(D\), respectively. In this paper, we study super-arc-connected and super-connected total digraphs. The following results are obtained:

1. \(T(D)\) is super-arc-connected if and only if \(D \ncong \overrightarrow{K_2}\).
2. If \(\kappa(D) + \lambda(D) > \delta(D) + 1\), then \(T(D)\) is super-connected.

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.