The complexity of the maximum leaf spanning tree problem for grid graphs is currently unknown. We determine the maximum number of leaves in a grid graph with up to \(4\) rows and with \(6\) rows. Furthermore, we give some constructions of spanning trees of grid graphs with a large number of leaves.

Let \((X, \mathcal{B})\) be a \(\lambda\)-fold \(G\)-decomposition of \(\lambda H\). Let \(G_i\), \(i=1,\ldots,\mu\), be all nonisomorphic proper subgraphs of \(G\) without isolated vertices. Put \(\mathcal{B}_i = \{B_i \mid B \in \mathcal{B}\}\), where \(B_i\) is a subgraph of \(B\) isomorphic to \(G_i\). A complete simultaneous metamorphosis of \((X, \mathcal{B})\) is a rearrangement, for each \(i = 1, \ldots, \mu\), of the edges of \(\bigcup_{B \in \mathcal{B}} (E(B) \setminus E(B_i))\) into a family \(\mathcal{F}_i\) of copies of \(G_i\) with a leave \(L_i\), such that \((X, \mathcal{B}_i \cup \mathcal{F}_i, L_i)\) is a maximum packing of \(\lambda H\) with copies of \(G_i\). In this paper, we give a complete answer to the existence problem of a \(\lambda\)-fold kite system having a complete simultaneous metamorphosis.

Whist tournaments for \( v \) players, \( \mathrm{Wh}(v) \), are known to exist for all \( v \equiv 0, 1 \pmod{4} \). In this paper, a new specialization of whist tournament design, namely a \({balanced\; whist\; tournament}\), is introduced. We establish that balanced whist tournaments on \( v \) players, \( \mathrm{BWh}(v) \), exist for several infinite classes of \( v \). An adaptation of a classic construction due to R. C. Bose and J. M. Cameron enables us to establish that \( \mathrm{BWh}(4n + 1) \) exist whenever \( 4n + 1 \) is a prime or a prime power. It is also established that \( \mathrm{BWh}(4n) \) exist for \( 4n = 2^k \), with \( k \equiv 0 \pmod{2, 3 \text{ or } 5} \). We demonstrate that a \( \mathrm{BWh}(4n + 1) \) is equivalent to a conference matrix of order \( 4n + 2 \). Consequently, a necessary condition for the existence of a \( \mathrm{BWh}(4n + 1) \) is that \( 4n + 1 \) is a product of primes each of which is \( \equiv 1 \pmod{4} \). Thus, in particular, \( \mathrm{BWh}(21) \) and \( \mathrm{BWh}(33) \) do not exist. Specific examples of \( \mathrm{BWh}(v) \) are given for \( v = 4, 8, 9, 20, 24, 32 \). It is also shown that a \( \mathrm{BWh}(12) \) does not exist.

Let \(\alpha(G)\) represent the maximal size of any product-free subset of a finite abelian group \(G\). It is well known that \(\alpha(G) = \frac{|G|}{3}\left(1 + \frac{1}{p}\right)\) if \(|G|\) is divisible by a prime \(p \equiv 2 \pmod{3}\) and \(p\) is the smallest such prime, \(\alpha(G) = \frac{|G|}{3}\) if \(|G|\) is not divisible by a prime \(p \equiv 2 \pmod{3}\) but \(3\) divides \(|G|\), and \(\alpha(G) = \frac{|G|}{3}\left(1 – \frac{1}{m}\right)\) if \(|G|\) is divisible only by primes \(p \equiv 1 \pmod{3}\) and \(m\) is the exponent of \(|G|\). In this paper, we use only basic group theory and number theory to derive exact expressions for the number of different maximal product-free subsets of \(G\) in the first two cases. The formulas are given in terms of the sizes of the subgroups of \(G\).

The \( P_3 \) intersection graph \( P_3(G) \) of a graph \( G \) is the intersection graph of all induced \( 3 \)-paths in \( G \). In this paper, we prove that any \( P_3 \)-convergent graph is \( P_3^n(G) \)-complete for some \( n \geq 1 \). Additionally, we prove that there are no \( P_3 \)-fixed graphs. The touching number, periodicity, and connectivity of \( P_3(G) \) are also studied.

This paper describes the study of a special class of 4-regular plane graphs that are Hamiltonian. These graphs are of particular interest in knot theory. An algorithm is presented that randomly generates such graphs with \( n \) vertices with a fixed (and oriented) Hamiltonian cycle in \( O(n) \) time. An exact count of the number of such graphs with \( n \) vertices is obtained, and the asymptotic growth rate of this number is determined. Numerical evidence is provided to show that the algorithm can be modified to generate these graphs with a near uniform probability. This can be considered a first step in generating large random knots without bias.

We enumerate nonisomorphic minimum genus orientable embeddings of the complete bipartite graph \( K_{m,n} \) for \( 2 \leq m, n \leq 7 \) except for \( (m, n) = (7, 7) \).

A complete coloring of a graph \( G \) is a proper vertex coloring of \( G \) with the property that for every two distinct colors \( i \) and \( j \) used in the coloring, there exist adjacent vertices of \( G \) colored \( i \) and \( j \). The maximum positive integer \( k \) for which \( G \) has a complete \( k \)-coloring is the achromatic number \( \psi(G) \) of \( G \).

A Grundy coloring of a graph \( G \) is a proper vertex coloring of \( G \) with the property that for every two colors (positive integers) \( i \) and \( j \) with \( i < j \), every vertex colored \( j \) has a neighbor colored \( i \). The maximum positive integer \( k \) for which a graph \( G \) has a Grundy \( k \)-coloring is the Grundy number \( \Gamma(G) \). Thus, \( 2 \leq \chi(G) \leq \Gamma(G) \leq \psi(G) \) for every nonempty graph \( G \). It is shown that if \( a, b, \) and \( c \) are integers with \( 2 \leq a \leq b \leq c \), then there exists a connected graph \( G \) with \( \chi(G) = a \), \( \Gamma(G) = b \), and \( \psi(G) = c \) if and only if \( a = b = c = 2 \) or \( b \geq 3 \).

A complete coloring of a graph \( G \) is a proper vertex coloring of \( G \) with the property that for every two distinct colors \( i \) and \( j \) used in the coloring, there exist adjacent vertices of \( G \) colored \( i \) and \( j \). The maximum positive integer \( k \) for which \( G \) has a complete \( k \)-coloring is the achromatic number \( \psi(G) \) of \( G \).

A Grundy coloring of a graph \( G \) is a proper vertex coloring of \( G \) with the property that for every two colors (positive integers) \( i \) and \( j \) with \( i < j \), every vertex colored \( j \) has a neighbor colored \( i \). The maximum positive integer \( k \) for which a graph \( G \) has a Grundy \( k \)-coloring is the Grundy number \( \Gamma(G) \). Thus, \( 2 \leq \chi(G) \leq \Gamma(G) \leq \psi(G) \) for every nonempty graph \( G \). It is shown that if \( a, b, \) and \( c \) are integers with \( 2 \leq a \leq b \leq c \), then there exists a connected graph \( G \) with \( \chi(G) = a \), \( \Gamma(G) = b \), and \( \psi(G) = c \) if and only if \( a = b = c = 2 \) or \( b \geq 3 \).

Let \( G \) be a simple graph, and let \( p \) be a positive integer. A subset \( D \subseteq V(G) \) is a \( p \)-dominating set of the graph \( G \) if every vertex \( v \in V(G) – D \) is adjacent to at least \( p \) vertices of \( D \). The \( p \)-domination number \( \gamma_p(G) \) is the minimum cardinality among the \( p \)-dominating sets of \( G \). Note that the \( 1 \)-domination number \( \gamma_1(G) \) is the usual domination number \( \gamma(G) \).

A subset \( S \subseteq V(G) \) is said to be a total dominating set if every vertex in \( V(G) \) has at least one neighbor in \( S \), and it is a connected dominating set if the graph induced by \( S \) is connected. The total domination number \( \gamma_t(G) \) represents the cardinality of a minimum total dominating set of \( G \) and the connected domination number \( \gamma_c(G) \) the cardinality of a minimum connected dominating set.

Fink and Jacobson showed in 1985 that if \( G \) is a graph with \( \Delta(G) \geq p \geq 2 \), then \(\gamma_p(G) \geq \gamma(G) + p – 2.\)
In this paper, we will give some sufficient conditions for a graph \( G \) such that \(\gamma_p(G) \geq \gamma(G) + p – 1.\)
We will show that for block graphs \( G \) the inequality \(\gamma_p(G) \geq \gamma_t(G) + p – 2 \) is valid and that for trees \( T \) the inequality \(\gamma_p(T) \geq \gamma_c(T) + p – 1\) holds. Further, we characterize the trees \( T \) with \(\gamma_p(T) = \gamma_c(T) + p – 1,\) \(\gamma_p(T) = \gamma_t(T) + p – 2, \gamma_p(T) = \gamma_t(T) + p – 1,\) and \(\gamma_p(T) = \gamma(T) + p – 1.\)