Let \(G\) be a finite simple \(\chi\)-chromatic graph and \(\mathcal{L} = \{L_u\}_{u\in V(G)}\) be a list assignment to its vertices with \(L_u \subseteq \{1,…,\chi\}\). A list colouring problem \((G, \mathcal{L})\) with a unique solution for which the sum \(\sum_{u\in V(G)}|L_u|\) is maximized, is called a \(maximum\; \chi-list \;assignment\) of \(G\). In this paper, we prove a \(Circuit\; Simulation\) Lemma that, strictly speaking, makes it possible to simulate any Boolean function by \(effective\) 3-colourings of a graph that is \(polynomial-time \;constructable\) from the Boolean function itself. We use the lemma to simply prove some old results as corollaries, and also we prove that the following decision problem, related to the computation of the fixing number of a graph [Daneshgar \(1997\), Daneshgar and Naserasr, Ars Combin. \(69\) \((2003)\)], is \(\sum_{2}^{P}\)-complete.

In this paper, we give another proof for labeled spanning forests of the complete bipartite graph \(K_{m,n}\), and obtain two Abel-type polynomials. And then we investigate the enumeration of non-trivial rooted labeled spanning forests of the complete bipartite graph \(K_{m,n}\).

In this paper, we investigate the global behavior of the difference equation

\[x_{n+1} = \frac{\alpha x_{n-k}}{\beta+\gamma x_{n-(k+1)}^p},\text{n=1,2,}\ldots\]

with non-negative parameters and non-negative initial conditions, where \(k\) is an odd number.

In many papers, the relation between the domination number of a product of graphs and the product of domination numbers of factors is studied. Here we investigate this problem for domination and total domination numbers in the cross product of digraphs. We give analogues of known results for graphs, and we also present new results for digraphs with sources. Using these results, we find domination (total domination) numbers for some classes of digraphs.

Let \(P_{k+1}\) denote a path of length \(k\) and let \(C_k\) denote a cycle of length \(k\). As usual, \(K_n\) denotes the complete graph on \(n\) vertices. In this paper, we investigate decompositions of \(K_n\) into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing \(K_n\) into \(p\) copies of \(P_5\) and \(q\) copies of \(C_4\) for all possible values of \(p\geq 0\) and \(q\geq 0\).

Given a simple connected undirected graph \(G\), the Wiener index \(W(G)\) of \(G\) is defined as half the sum of the distances over all pairs of vertices of \(G\). In practice, \(G\) corresponds to what is known as the molecular graph of an organic compound. We obtain a sharp lower bound for \(W(G)\) of an arbitrary graph in terms of the order, size, and diameter of \(G\).

The Zagreb indices are topological indices of graphs, which are defined as:\(M_1(G) = \sum\limits_{v \in V(G)} (d(v))^2\), \(M_2(G) = \sum\limits_{uv \in E(G)} d(u)d(v)\) .In this paper, we determine the upper and lower bounds for the Zagreb indices of unicyclic graphs in terms of their order and girth. In each case, we characterize the extremal graphs.

In this paper, we are concerned with Leibniz numbers. We establish a series of identities involving Leibniz numbers, Stirling numbers, harmonic numbers, arctan numbers by making use of generating functions. In addition, we give the asymptotic expansion of certain sums related to Leibniz numbers by Laplace’s method.

We consider the undirected simple connected graph for which edges fail independently of each other with equal probability \(1 – p\) and nodes are perfect. The all-terminal reliability of a graph \(G\) is the probability that the spanning subgraph of surviving edges is connected, denoted as \(R(G,p)\). Graph \(G \in \Omega(n,e)\) is said to be uniformly least reliable if \(R(G,p) \leq R(G’,p)\) for all \(G’ \in \Omega(n,e)\), and for all edge failure probabilities \(0 < 1 – p < 1\). In this paper, we prove the existence of uniformly least reliable graphs in the class \(\Omega(n,e)\) for \(e \leq n + 1\) and give their topologies.

We study V- and \(\Lambda\)-patterns which generalize valleys and peaks, as well as increasing and decreasing runs, in permutations. A complete classification of permutations (multi)-avoiding V- and \(\Lambda\)-patterns of length \(4\) is given. We also establish a connection between restricted permutations and matchings in the coronas of complete graphs.