For a graph \( G = (V, E) \), a non-empty set \( S \subseteq V \) is a global offensive alliance (respectively, global strong offensive alliance) if for every vertex \( v \in V – S \), at least half of the vertices in its closed neighborhood are in \( S \) (respectively, a strict majority of its closed neighborhood are in \( S \)). The global offensive alliance number \( \gamma_o(G) \) (respectively, global strong offensive alliance number \( \gamma_{\hat{o}}(G) \)) is the minimum cardinality of a global offensive alliance (respectively, global strong offensive alliance) of \( G \). In this paper, we determine an upper bound on each parameter for bipartite graphs without isolated vertices. More precisely, we show that \( \gamma_o(G) \leq \frac{n – \ell + s}{2} \) and \( \gamma_{\hat{o}}(G) \leq \frac{n + \ell}{2} \), where \( n \), \( \ell \), and \( s \) are the order, the number of leaves, and the support vertices of \( G \), respectively. Moreover, extremal trees attaining each bound are characterized.

There is a hypothesis that a non-self-centric radially-maximal graph of radius \( r \) has at least \( 3r – 1 \) vertices. Moreover, if it has exactly \( 3r – 1 \) vertices, then it is planar with minimum degree \( 1 \) and maximum degree \( 3 \). Using an enhanced exhaustive computer search, we prove this hypothesis for \( r = 4, 5 \).

A vertex set \( X \) of a simple graph is called OO-irredundant if for each \( v \in X \), \( N(v) – N(X – \{v\}) \neq \emptyset \). Basic results for maximal OO-irredundant sets of a graph are obtained.

A set of necessary conditions for the existence of a partition of \(\{1, \ldots, 2m – 1, L\}\) into differences \(d, d + 1, \ldots, d + m – 1\) is \((m, L) \equiv (0, 0), (1, d + 1), (2, 1), (3, d) \pmod{(4, 2)}\) and \(m \geq 2d – 2\) or \(m = 1\). If \(m = 2d – 2\) then \(L = 5d – 5\), if \(m = 2d – 1\) then \(4d – 2 \leq L \leq 6d – 4\) and if \(m \geq 2d\) then \(2m \leq L \leq 3m + d – 2\). Similar conditions for the partition of \(\{1, \ldots, 2m, L\} \setminus \{2\}\) into differences \(d, d + 1, \ldots, d + m – 1\) are \((m, L) \equiv (0, 0), (1, d + 1), (2, 1), (3, d) \pmod{(4, 2)}\), \((d, m, L) \neq (1, 1, 4), (2, 3, 8)\) and \(m \geq 2d – 2\), \(m = 1\) or \((d, m, L) = (3, 2, 7), (3, 3, 9)\). If \(m = 2d – 2\) then \(L = 5d – 5, 5d – 3\), if \(m = 2d – 1\) then \(4d – 1 \leq L \leq 6d – 2\) and if \(m \geq 2d\) then \(2m + 1 \leq L \leq 3m + d – 1\).

It is shown that for many cases when the necessary conditions hold, the set \(\{1, \ldots, 2m – 1, L\}\) and \(\{1, \ldots, 2m – 1, L\} \setminus \{2\}\) can be so partitioned. These partitions exist for all the minimum and maximum \(L\), when \(d \leq 3\), when \(m = 1\) and when \(m \geq 8d – 3\) (\(m \geq 8d + 4\) in the hooked case). The constructions given fully solve the existence of these partitions if the necessary conditions for the existence of extended and hooked extended Langford sequences are sufficient.

Let \( n \) and \( q \) be positive integers, with \( n \geq 3 \), and let \( N = nq \). As input, we are to be given an arbitrary ordered \( n \)-sequence \( x_1, x_2, \ldots, x_n \), where \( 1 \leq x_i \leq N \) for all \( i \). We are to be presented with this sequence one entry at a time. As each entry is received, it must be placed into one of the positions \( 1, 2, \ldots, n \), where it must remain. A natural way to do this, in an attempt to sort the input sequence, is as follows. For any integer \( x \in \{1, \ldots, N\} \), we let \( s(x) \) denote the unique integer \( s \) for which \( (s-1)q + 1 \leq x \leq sq \). When we receive the entry \( x_i \), we consider those positions still unoccupied after having placed the previous \( i-1 \) entries, and we place \( x_i \) into the one which is closest to \( s(x_i) \). In the event of a tie for closest, we choose the higher of the two positions. We refer to this procedure as the \({placement\; algorithm}\). Regarding this algorithm, we consider the following question: for how many input sequences will the last two positions filled be positions \( 1 \) and \( n \)? We show that this number is \( (n-1)^{n-3}n^2q^n \).

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.\)

Let \( G = (V, E) \) be a connected graph. A dominating set \( S \) of \( G \) is called a neighborhood connected dominating set (\({ncd-set}\)) if the induced subgraph \( \langle N(S) \rangle \) is connected. The minimum cardinality of an ncd-set of \( G \) is called the neighborhood connected domination number of \( G \) and is denoted by \( \gamma_{nc}(G) \). In this paper, we initiate a study of this parameter.

Let \( \lambda K_v \) be the complete multigraph, and \( G \) a finite simple graph. A \( G \)-design (\( G \)-packing, \( G \)-covering, respectively) of \( \lambda K_v \) is denoted by \( GD(v, G, \lambda) \) (\( PD(v, G, \lambda) \), \( CD(v, G, \lambda) \), respectively). In this paper, we will give some construction methods of graph packings and graph coverings, determine the existence spectrum for the \( G \)-designs of \( \lambda K_v \), and construct the maximum packings and the minimum coverings of \( \lambda K_v \) with \( G \) for any positive integer \( \lambda \). The graph \( G \) is either \( (K_4 – e) \cup P_1 \) or \( C_5 \bigodot P_1 \). Therefore, the problems of \( G \)-coverings and \( G \)-packings of \( \lambda K_v \) are solved completely when \( G \) is a graph with order \( 6 \) and \( |E(G)| \leq 6 \).

A maximal directed path in an acyclic orientation of a graph \( G \) is a path \( a_1 \to a_2 \to \cdots \to a_k \) such that \( \text{id}\; a_1 = \text{od}\; a_k = 0 \). The compression of \( G \) is the smallest integer \( k \) such that, for any acyclic orientation of \( G \), there is a maximal directed path of length at most \( k \). We characterize graphs with compression \( 1 \) and \( 2 \) and determine the compression of trees.

The generalized deBruijn graph \(dB(a,k)\) is the directed graph with \(a^k\) vertices and edges between vertices \(x = a_1, a_2, \ldots, a_k\) and \(y = b_1, b_2, \ldots, b_k\) precisely when \(a_2\cdots a_k = b_1,b_2\cdots b_{k-1}\). The deBruijn graphs can be further generalized by introducing an overlap variable \(t \leq k-1\) where the number of consecutive digits by which the vertex labels (sequences) overlap is \(t\). The \(\alpha\)-overlap graph is the underlying simple graph of the generalized deBruijn digraph with vertex label overlap \(0 t > 0\). Thus \(dB(a,k) = G(a,k,k-1)\). In this paper, we show that every \(\alpha\)-overlap graph is \(3\)-colorable for any \(a\) if \(k\) is sufficiently large. We also determine bounds on the chromatic number of the \(\alpha\)-overlap graphs if \(a\) is much larger than \(k\).