In Algebraic Graph Theory, Biggs \([2]\) gives a method for finding the chromatic polynomial of any connected graph by computing the Tutte polynomial. It is used by Biggs \([2]\) to compute the chromatic polynomial of Peterson’s graph. In \(1972\) Sands \([4]\) developed a computer algorithm using matrix operations on the incidence matrix to compute the Tutte Polynomial. In \([1]\), Anthony finds the worst-case time-complexity of computing the Tutte Polynomial. This paper shows a method using group-theoretical properties to compute the Tutte polynomial for Cayley graphs which improves the time-complexity.

Let \(N({Z})\) denote the set of all positive integers (integers). The sum graph \(G_S\) of a finite subset \(S \subset N({Z})\) is the graph \((S, E)\) with \(uv \in E\) if and only if \(u+v \in S\). A graph \(G\) is said to be an (integral) sum graph if it is isomorphic to the sum graph of some \(S \subset N({Z})\). The (integral) sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices which when added to \(G\) result in an (integral) sum graph. A mod (integral) sum graph is a sum graph with \(S \subset {Z}_m \setminus \{0\}\) (\(S \subset {Z}_m\)) and all arithmetic performed modulo \(m\) where \(m \geq |S|+1\) (\(m \geq |S|\)). The mod (integral) sum number \(\rho(G)\) of \(G\) is the least number \(\rho\) (\(\psi\)) of isolated vertices \(\rho K_1\) (\(\psi K_1\)) such that \(G \cup \rho K_1\) (\(G \cup \psi K_1\)) is a mod (integral) sum graph. In this paper, the mod (integral) sum numbers of \(K_{r,s}\) and \(K_n – E(K_r)\) are investigated and bounded, and \(n\)-spoked wheel \(W_n\) is shown to be a mod integral sum graph.

In this paper, the forcing domination numbers of the graphs \(P_n \times P_3\) and \(C_n \times P_3\) are completely determined. This improves the previous results on the forcing domination numbers of \(P_n \times P_2\) and \(C_n \times P_2\).

The stabilizers of the minimum-weight codewords of the binary codes obtained from the strongly regular graphs \(T(n)\) defined by the primitive rank-\(3\) action of the alternating groups \(A_n\), where \(n \geq 5\), on \(\Omega^{(2)}\), the set of duads of \(\Omega = \{1,2,\ldots,n\}\) are examined. For a codeword \(w\) of minimum-weight in the binary code \(C\) obtained as stated above, from an adjacency matrix of the triangular graph \(T(n)\) defined by the primitive rank-3 action of the alternating groups \(A_n\) where \(n \geq 5\), on \(\Omega^{(2)}\), the set of duads of \(\Omega = \{1,2,\ldots,n\}\), we determine the stabilizer \(Aut(C)_w\) in \(Aut(C)\) and show that \(Aut(C)_w\) is a maximal subgroup of \(Aut(C)\).

For a graph \(G\), let \(\mathcal{D}(G)\) be the set of strong orientations of \(G\). Define \(\overrightarrow{d}(G) = \min\{d(D) \mid D \in \mathcal{D}(G)\}\) and \(\rho(G) = \overrightarrow{d}(G) – d(G)\), where \(d(D)\) (resp. \(d(G)\)) denotes the diameter of the digraph \(D\) (resp. graph \(G\)). In this paper, we determine the exact value of \(\rho(K_r \times K_s)\) for \(r \leq s\) and \((r,s) \not\in \{(3,5), (3,6), (4,4)\}\), where \(K_r \times K_s\) denotes the tensor product of \(K_r\) and \(K_s\). Using the results obtained here, a known result on \(\rho(G)\), where \(G\) is a regular complete multipartite graph is deduced as corollary.

A two-step approach to finding knight covers for an \(N \times N\) chessboard eliminates the problem of detecting duplicate partial solutions. The time and storage needed to generate solutions is greatly reduced. The method can handle boards as large as \(45 \times 45\) and has matched or beaten all previously known solutions for every board size tried.

In this paper we prove that there exists a strong critical set of size \(m\) in the back circulant latin square of order \(n\) for all \(\frac{n^2-1}{2} \leq m \leq \frac{n^2-n}{2}\), when \(n\) is odd. Moreover, when \(n\) is even we prove that there exists a strong critical set of size \(m\) in the back circulant latin square of order \(n\) for all \(\frac{n^2-n}{2}-(n-2) \leq m \leq \frac{n^2-n}{2}\) and \(m \in \{\frac{n^2}{4}, \frac{n^2}{4}+2, \frac{n^2}{4}+4, \ldots, \frac{n^2-n}{2}-n\}\).

In this paper, a characterization of two classes of \((q, q+1)\)-geometries, that are fully embedded in a projective space \(PG(n, q)\), is obtained. The first class is the one of the \((q,q+1)\)-geometry \(H^{n,m}_q\), having points the points of \(PG(n, q)\) that are not contained in an \(m\)-dimensional subspace \(\Pi[m]\) of \(PG(n, q)\), for \(0 \leq m \leq n-3\), and lines the lines of \(PG(n, q)\) skew to \(\Pi[m]\). The second class is the one of the \((q,q+1)\)-geometry \(SH^{n,m}_q\), having the same point set as \(H^{n,m}_q\), but with \(-1 \leq m \leq n-3\), and lines the lines skew to \(\Pi^{n,m}_q\) that are not contained in a certain partition of the point set of \(SH^{n,m}_q\). Our characterization uses the axiom of Pasch, which is also known as axiom of Veblen-Young. It is a generalization of the characterization for partial geometries satisfying the axiom of Pasch by J. A. Thas and F. De Clerck. A characterization for \(H^{n,m}_q\) was already proved by H. Cuypers. His result however does not include \(SH^{n,m}_q\).