The size of a minimum total dominating set in the \(m \times n\) grid graph is denoted by \(\gamma_t(P_m \square P_n)\). Here a dynamic programming algorithm that computes \(\gamma_t(P_m \square P_n)\) for any \(m\) and \(n\) is presented, and it is shown how properties of the algorithm can be used to derive formulae for a fixed, small value of \(m\). Using this method, formulae for \(\gamma_t(P_m \square P_n)\) for \(m \leq 28\) are obtained. Formulae for larger \(m\) are further conjectured, and a new general upper bound on \(\gamma_t(P_m \square P_n)\) is proved.

The 2-cell embeddings of graphs on closed surfaces have been widely studied. It is well known that (2-cell) embedding a given graph \(G\) on a closed orientable surface is equivalent to cyclically ordering the darts incident to each vertex of \(G\). In this paper, we study the following problem: given a genus \(g\) embedding \(\in\) of the graph \(G\) and a vertex of \(G\), how many different ways of reembedding the vertex such that the resulting embedding \(\in’\) is of genus \(g + \Delta g\)? We give formulas to compute this quantity and the local minimal genus achieved by reembedding. In the process, we obtain miscellaneous results. In particular, if there exists a one-face embedding of \(G\), then the probability of a random embedding of \(G\) to be one-face is at least \(\prod_{v \in V(G)} \frac{2}{\deg(v) + 2}\) where \(\deg(v)\) denotes the vertex degree of \(v\). Furthermore, we obtain an easy-to-check necessary condition for a given embedding of \(G\) to be an embedding of minimum genus.

We show that all but \(4489\) integers \(n\) with \(4 < n \leq 4 \cdot 10^{30}\) cannot occur as the order of a circulant Hadamard matrix. Our algorithm allows us to search \(10000\) times farther than prior efforts, while substantially reducing memory requirements. The principal improvement over prior methods involves the incorporation of a separate search for double Wieferich prime pairs \(\{p, q\}\), which have the property that \(p^{q-1} \equiv 1 \pmod{q^2}\) and \(q^{p-1} \equiv 1 \pmod{p^2}\).

A graph \( G = (V, E) \) is word-representable if there exists a word \( w \) over the alphabet \( V \) such that letters \( x \) and \( y \) alternate in \( w \) if and only if \( (x, y) \) is an edge in \( E \).

A recent elegant result of Akrobotu \( et \, al. \) \([1]\) states that a triangulation of any convex polyomino is word-representable if and only if it is 3-colourable. In this paper, we generalize a particular case of this result by showing that the result of Akrobotu \( et \, al. \) \([1]\) is true even if we allow a domino tile, instead of having just \(1 \times 1\) tiles on a rectangular polyomino.

The eternal domination number of a split graph is shown to equal either its domination number, or its domination number plus one. A characterization of the split graphs which achieve equality in either instance is given. It is shown that the problem of deciding whether the domination number of a Hamiltonian split graph is at most a given integer \(k\) is NP-complete, as is the problem of deciding whether the eternal domination number of a Hamiltonian split graph is at most a given integer \(k\). Finally, the problem of computing the eternal domination number is shown to be polynomial for any subclass of split graphs for which the domination number can be computed in polynomial time, in particular for strongly chordal split graphs.

A graceful labeling of a graph \( G \) of order \( n \) and size \( m \) is a one-to-one function \( f : V(G) \rightarrow \{0, 1, \ldots, m\} \) that induces a one-to-one function \( f’ : E(G) \rightarrow \{1, 2, \ldots, m\} \) defined by \( f'(uv) = |f(u) – f(v)| \). A graph that admits a graceful labeling is a graceful graph. A proper coloring \( c : V(G) \rightarrow \{1, 2, \ldots, k\} \) is called a graceful \( k \)-coloring if the induced edge coloring \( c’ \) defined by \( c'(uv) = |c(u) – c(v)| \) is proper. The minimum positive integer \( k \) for which \( G \) has a graceful \( k \)-coloring is its graceful chromatic number \( \chi_g(G) \). The graceful chromatic numbers of cycles, wheels, and caterpillars are determined. An upper bound for the graceful chromatic number of trees is determined in terms of its maximum degree.

For a graph \( G = (V, E) \) with a coloring \( f : V(G) \rightarrow \mathbb{Z}_2 \), let \( v_f(i) = |f^{-1}(i)| \). We say \( f \) is friendly if \( |v_f(1) – v_f(0)| \leq 1 \). The coloring \( f \) induces an edge labeling \( f_+ : E \rightarrow \mathbb{Z}_2 \) defined by \( f_+(uv) = f(u) + f(v) \mod 2 \), for each \( uv \in E \). Let \( e_f = |f_+^{-1}(i)| \). The friendly index set of the graph \( G \), denoted by \( FI(G) \), is defined by \(\{|e_f(1) – e_f(0)| : f \text{ is a friendly coloring of } G \}\). We say \( G \) is fully cordial if \( FI(G) = \{|E|, |E| – 2, |E| – 4, \ldots, |E| – 2[\binom{|E|}{2}]\} \). In this paper, we develop a new technique to calculate friendly index sets without labeling vertices, and we develop a technique to create fully cordial graphs from smaller fully cordial graphs. In particular, we show the first examples of fully cordial graphs that are not trees, as well as new infinite classes of fully cordial graphs.

This paper studies the unitary Cayley graph associated with the ring of dual numbers, \(\mathbb{Z}_n[\alpha]\). It determines the exact diameter, vertex chromatic number, and edge chromatic number. In addition, it classifies all perfect graphs within this class.

Stanton-type graphs were introduced recently. In this paper, we define generalized Stanton-type graphs. We also identify LO and OE graphs, find the minimum \(\lambda\) for decomposition of \(\lambda K_n\) into these graphs, and show that for all viable values of \(\lambda\), the necessary conditions are sufficient for LO- and OE-decompositions using cyclic decompositions from base graphs.

For a finite graph \(G\) with vertices \(\{v_1, \ldots, v_r\}\), a representation of \(G\) modulo \(n\) is a set \(\{a_1, \ldots, a_r\}\) of distinct, nonnegative integers with \(0 \leq a_i < n\), satisfying \(\gcd(a_i – a_j, n) = 1\) if and only if \(v_i\) is adjacent to \(v_j\). The representation number, \(Rep(G)\), is the smallest \(n\) such that \(G\) has a representation modulo \(n\). Evans \(et \, al.\) obtained the representation number of paths. They also obtained the representation number of a cycle except for cycles of length \(2^k + 1\), \(k \geq 3\). In the present paper, we obtain upper and lower bounds for the representation number of a caterpillar, and get its exact value in some cases.