A question involving a chess piece called a prince on the \(8\times 8\) chessboard leads to a concept in graph theory involving total domination in the Cartesian products of paths and cycles. A vertex \(u\) in a graph \(G\) totally dominates a vertex \(v\) if \(v\) is adjacent to \(u\). A subset \(S\) of the vertex set of a graph \(G\) is a total dominating set for \(G\) if every vertex of \(G\) is totally dominated by at least one vertex of \(S\). If \(S\) is a total dominating set of a graph \(G\), then \(S(v)\) denotes the number of vertices in \(S\) that totally dominate \(v\). A total dominating set \(S\) in a graph \(G\) is called a proper total dominating set if \(S(u) \ne S(v)\) for every two adjacent vertices \(u\) and \(v\) of \(G\). It is shown that \(C_n \ \Box \ K_2\) possesses a proper total dominating set if and only if \(n\ge 4\) is even and the graph \(C_n \ \Box \ P_m\) possesses a proper total dominating set for every even integer \(n \ge 4\) and every integer \(m \ge 3\). Furthermore, \(C_3 \ \Box \ P_m\) possesses a proper total dominating set if and only if \(m = 3\). If \(n\ge 5\) is an odd integer and \(m\equiv 3 \pmod 4\), then \(C_n \ \Box \ P_m\) has a proper total dominating set. If at least one of \(n\) and \(m\) is even, then \(C_n \ \Box \ C_m\) has a proper total dominating set. The graphs \(C_n \ \Box \ C_m\) are further studied when both \(n\) and \(m\) are odd. Other results and questions are also presented.

For a graph \(F\) and a positive integer \(t\), the vertex-disjoint Ramsey number \(VR_t(F)\) is the minimum positive integer \(n\) such that every red-blue coloring of the edges of the complete graph \(K_n\) of order \(n\) results in \(t\) pairwise vertex-disjoint monochromatic copies of subgraphs isomorphic to \(F\), while the edge-disjoint Ramsey number \(ER_t(F)\) is the corresponding number for edge-disjoint subgraphs. These numbers have been investigated for the three connected graphs \(K_3\), \(P_4\) and \(K_{1, 3}\) of size 3. For two vertex-disjoint graphs \(G\) and \(H\), let \(G+H\) denote the union of \(G\) and \(H\). Here we study these numbers for the two disconnected graphs \(3K_2\) and \(P_3+P_2\) of size 3. It is shown that \(VR_t(3K_2)= 6t+2\) and \(VR_t(P_3+P_2)= 5t+1\) for every positive integer \(t\). The numbers \(ER_t(3K_2)\) and \(ER_t(P_3+P_2)\) are determined for \(t \le 4\) and bounds are established for \(ER_t(3K_2)\) and \(ER_t(P_3+P_2)\) when \(t \ge 5\). Other results and problems are presented as well.

Every red-blue coloring of the edges of a graph \(G\) results in a sequence \(G_1\), \(G_2\), \(\ldots\), \(G_{\ell}\) of pairwise edge-disjoint monochromatic subgraphs \(G_i\) (\(1 \le i \le \ell\)) of size \(i\) such that \(G_i\) is isomorphic to a subgraph of \(G_{i+1}\) for \(1 \le i \le \ell-1\). Such a sequence is called a Ramsey chain in \(G\) and \(AR_c(G)\) is the maximum length of a Ramsey chain in \(G\) with respect to a red-blue coloring \(c\). The Ramsey index \(AR(G)\) of \(G\) is the minimum value of \(AR_c(G)\) among all red-blue colorings \(c\) of \(G\). Several results giving the Ramsey indexes of graphs are surveyed. A galaxy is a graph each of whose components is a star. Results and conjectures on Ramsey indexes of galaxies are presented.

An edge-coloring of a graph \(G\) with natural numbers \(1,2,\ldots\) is called a sum edge-coloring if the colors of edges incident to any vertex of \(G\) are distinct and the sum of the colors of the edges of \(G\) is minimum. The edge-chromatic sum of a graph \(G\) is the sum of the colors of edges in a sum edge-coloring of \(G\). In general, the problem of finding the edge-chromatic sum of an \(r\)-regular (\(r\geq 3\)) graph is \(NP\)-complete. In this paper we provide some bounds on the edge-chromatic sums of various products of graphs. In particular, we give tight upper bounds on the edge-chromatic sums of tensor, strong tensor, Cartesian, strong products and composition of graphs. We also determine the edge-chromatic sums and edge-strengths of the Cartesian products of regular graphs and paths (cycles) with an even number of vertices. Finally, we determine the edge-chromatic sums and edge-strengths of grids, cylinders, and tori.

Generalised nice sets are defined as subsets of edges of the extended Fano plane satisfying a certain absorbing property. The classification up to collineations, purely combinatorial in nature, provides 245 generalised nice sets. In turn, this gives rise to new Lie algebras obtained by modifying the bracket of homogeneous elements on an initial \(\mathbb Z_2^3\)-graded Lie algebra.

Let \(\alpha(n)\) denote the number of perfect square permutations in the symmetric group \(S_n\). The conjecture \(\alpha(2n+1) = (2n+1) \alpha(2n)\), provided by Stanley [4], was proved by Blum [1] using generating functions. However, several structural questions about these special permutations remained open. This paper presents an alternative and constructive proof for this conjecture, which highlights the deeper interplay between cycle structures and square properties. At the same time, we demonstrate that all permutations with an even number of even cycles in both \(S_{2n}\) and \(S_{2n+1}\) can be categorized into three disjoint types that correspond to each other.

In this paper, we generalize the \(k\)-Jacobsthal sequences and call them the generalized \((k,t)\)-Jacobsthal \(p\)-sequences. Also, we obtain combinatorial identities. Then, the generalized\((k,t)\)-Jacobsthal \(p\)-matrix is used to factorize the Pascal matrix. Finally, using the Riordan method, we obtain two factorizations of the Pascal matrix involving the generalized \((k,t)\)-Jacobsthal \(p\)-sequences.

An open-dominating set \(S\) for a graph \(G\) is a subset of vertices where every vertex has a neighbor in \(S\). An open-locating-dominating set \(S\) for a graph \(G\) is an open-dominating set such that each pair of distinct vertices in \(G\) have distinct set of open-neighbors in \(S\). We consider a type of a fault-tolerant open-locating dominating set called error-detecting open-locating-dominating sets. We present more results on the topic including its NP-completeness proof, extremal graphs, and a characterization of cubic graphs that permit an error-detecting open-locating-dominating set.

In this paper, we explore some interesting applications of the matrix tree theorem. In particular, we present a combinatorial interpretation of a distribution of \((n-1)^{n-1}\), in the context of uprooted spanning trees of the complete graph \(K_{n}\), which was previously obtained by Chauve–Dulucq–Guibert. Additionally, we establish a combinatorial explanation for the distribution of \(m^{n-1}n^{m-1}\), related to spanning trees of the complete bipartite graph \(K_{m,n}\), which seems new. Furthermore, we extend this study to the graph \(K_{n}\setminus \{e_{1,n}\}\), obtained by deleting an edge from \(K_n\), and derive a new identity for the number of its uprooted spanning trees.

The domatic number of a graph is the maximum number of pairwise disjoint dominating sets admitted by the graph. We introduce a game based around this graph invariant. The domatic number game is played on a graph \(G\) by two players, Alice and Bob, who take turns selecting a vertex and placing it into one of \(k\) sets. Alice is trying to make each of these sets into a dominating set of \(G\) while Bob’s goal is to prevent this from being accomplished. The maximum \(k\) for which Alice can achieve her goal when both players are playing optimal strategies, is called the game domatic number of \(G\). There are two versions of the game and two resulting invariants depending on whether Alice or Bob is the first to play. We prove several upper bounds on these game domatic numbers of arbitrary graphs and find the exact values for several classes of graphs including trees, complete bipartite graphs, cycles and some narrow grid graphs. We pose several open problems concerning the effect of standard graph operations on the game domatic number as well as a vexing question related to the monotonicity of the number of sets available to Alice.