In this paper, we consider the effect of edge contraction on the domination number and total domination number of a graph. We define the (total) domination contraction number of a graph as the minimum number of edges that must be contracted in order to decrease the (total) domination number. We show that both of these two numbers are at most three for any graph. In view of this result, we classify graphs by their (total) domination contraction numbers and characterize these classes of graphs.

In this paper, connected graphs with the largest Laplacian eigenvalue at most \(\frac{5+\sqrt{13}}{2}\) are characterized. Moreover, we prove that these graphs are determined by their Laplacian spectrum.

An extended directed triple system of order \(v\) with an idempotent element (EDTS(\(v, a\))) is a collection of triples of the type \([x, y, z]\), \([x, y, x]\) or \((x, x, x)\) chosen from a \(v\)-set, such that every ordered pair (not necessarily distinct) belongs to only one triple and there are \(a\) triples of the type \((x, x, x)\). If such a design with parameters \(v\) and \(a\) exists, then it will have \(b_{v,a}\) blocks, where \(b_{v,a} = (v^2 + 2a)/3\). A necessary and sufficient condition for the existence of EDTS(\(v, 0\)) and EDTS(\(v, 1\)) are \(v \equiv 0 \pmod{3}\) and \(v \not\equiv 0 \pmod{3}\), respectively. In this paper, we have constructed two EDTS(\(v, a\))’s such that the number of common triples is in the set \(\{0, 1, 2, \ldots, b_{v,a} – 2, b_{v,a}\}\), for \(a = 0, 1\).

As applications of the Anzahl theorems in finite orthogonal spaces, we study the critical problem of totally isotropic subspaces, and obtain the critical exponent.

Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is chromatically unique if for any graph \(H\), \(P(H,\lambda) = P(G, \lambda)\) implies H is isomorphic to \(G\). In this paper, we study the chromaticity of Turén graphs with deleted edges that induce a matching or a star. As a by-product, we obtain new families of chromatically unique graphs.

Let \(\{w_n\}\) be a second-order recurrent sequence. Several identities about the sums of products of second-order recurrent sequences were obtained and the relationship between the second-order recurrent sequences and the recurrence coefficient revealed. Some identities about Lucas sequences, Lucas numbers, and Fibonacci numbers were also obtained.

In this paper, we prove that for any positive integers \(k,n\) with \(k \geq 2\) , the graph \(P_k^n\) is a divisor graph if and only if \(n \leq 2k + 2\) , where \(P^k_n\) is the \(k\) th power of the path \(P_n\). For powers of cycles we show that \(C^k_n\) is a divisor graph when \(n \leq 2k + 2\), but is not a divisor graph when \(n \geq 2k + 2\),but is not a divisor graph when \(n\geq 2k+\lfloor \frac{k}{2}\rceil,\) where \(C^k_n\) is the \(k\)th power of the cycle \(C_n\). Moreover, for odd \(n\) with \(2k+2 < n < 2k + \lfloor\frac{k}{2}\rfloor + 3\), we show that the graph \(C^k_n\) is not a divisor graph.

The Wiener index of a graph \(G\) is defined as \(W(G) = \sum_{u,v \in V(G)} d_G(u,v),\) where \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G\) and the sum goes over all pairs of vertices. In this paper, we investigate the Wiener index of unicyclic graphs with given girth and characterize the extremal graphs with the minimal and maximal Wiener index.

In this paper, we consider a random mapping, \(\hat{T}_n\), of the finite set \(\{1,2,\ldots,n\}\) into itself for which the digraph representation \(\hat{G}_n\) is constructed by:\((1)\) selecting a random number, \(\hat{L}_n\), of cyclic vertices,\((2)\) constructing a uniform random forest of size \(n\) with the selected cyclic vertices as roots, and \((3)\) forming `cycles’ of trees by applying a random permutation to the selected cyclic vertices.We investigate \(\hat{k}_n\), the size of a `typical’ component of \(\hat{G}_n\), and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of \(k\), conditioned on \(\hat{L}_n = m(n)\). As an application of our results, we show in Section \(3\) that provided \(\hat{L}_n\) is of order much larger than \(\sqrt{n}\), then the joint distribution of the normalized order statistics of the component sizes of \(\hat{G}_n\) converges to the Poisson-Dirichlet \((1)\) distribution as \(n \to \infty\). Other applications and generalizations are also discussed in Section \(3\).

De Bruijn digraphs and shuffle-exchange graphs are useful models for interconnection networks. They can be represented as group action graphs of the wrapped butterfly graph and the cube-connected cycles, respectively. The Kautz digraph has similar definitions and properties to de Bruijn digraphs. It is \(d\)-regular and strongly \(d\)-connected, thus it is a group action graph. In this paper, we use another representation of the Kautz digraph and settle the open problem posed by M.-C. Heydemann in \([6]\).