A hypergraph \( H \) with vertex set \( V \) and edge set \( E \) is called bipartite if \( V \) can be partitioned into two subsets \( V_1 \) and \( V_2 \) such that \( e \cap V_1 \neq \phi \) and \( e \cap V_2 \neq \phi \) for any \( e \in E \). A bipartite self-complementary 3-uniform hypergraph \( H \) with partition \( (V_1, V_2) \) of a vertex set \( V \) such that \( |V_1| = m \) and \( |V_2| = n \) exists if and only if either (i) \( m = n \) or (ii) \( m \neq n \) and either \( m \) or \( n \) is congruent to 0 modulo 4 or (iii) \( m \neq n \) and both \( m \) and \( n \) are congruent to 1 or 2 modulo 4.

In this paper we prove that, there exists a regular bipartite self-complementary 3-uniform hypergraph \( H(V_1, V_2) \) with \( |V_1| = m, |V_2| = n, m + n > 3 \) if and only if \( m = n \) and \( n \) is congruent to 0 or 1 modulo 4. Further we prove that, there exists a quasi-regular bipartite self-complementary 3-uniform hypergraph \( H(V_1, V_2) \) with \( |V_1| = m, |V_2| = n, m + n > 3 \) if and only if either \( m = 3, n = 4 \) or \( m = n \) and \( n \) is congruent to 2 or 3 modulo 4.

Neighborhood-prime labeling is a variation of prime labeling. A labeling \( f : V(G) \to [|V(G)|] \) is a neighborhood-prime labeling if for each vertex \( v \in V(G) \) with degree greater than 1, the greatest common divisor of the set of labels in the neighborhood of \( v \) is 1. In this paper, we introduce techniques for finding neighborhood-prime labelings based on the Hamiltonicity of the graph, by using conditions on possible degrees of vertices, and by examining a neighborhood graph. In particular, classes of graphs shown to be neighborhood-prime include all generalized Petersen graphs, grid graphs of any size, and lobsters given restrictions on the degree of the vertices. In addition, we show that almost all graphs and almost all regular graphs have neighborhood-prime, and we find all graphs of this type.

Let \( A(n, d, w) \) denote the maximum size of a binary code with length \( n \), minimum distance \( d \), and constant weight \( w \). The following lower bounds are here obtained in computer searches for codes with prescribed automorphisms: \( A(16, 4, 6) \geq 624 \), \( A(19, 4, 8) \geq 4698 \), \( A(20, 4, 8) \geq 7830 \), \( A(21, 4, 6) \geq 2880 \), \( A(22, 6, 6) \geq 343 \), \( A(24, 4, 5) \geq 1920 \), \( A(24, 6, 9) \geq 3080 \), \( A(24, 6, 11) \geq 5376 \), \( A(24, 6, 12) \geq 5558 \), \( A(25, 4, 5) \geq 2380 \), \( A(25, 6, 10) \geq 6600 \), \( A(26, 4, 5) \geq 2816 \), and \( A(27, 4, 5) \geq 3456 \).

For a finite simple graph \( G \), say \( G \) is of dimension \( n \), and write \( \text{dim}(G) = n \), if \( n \) is the smallest integer such that \( G \) can be represented as a unit-distance graph in \( \mathbb{R}^n \). Define \( G \) to be \emph{dimension-critical} if every proper subgraph of \( G \) has dimension less than \( G \). In this article, we determine exactly which complete multipartite graphs are dimension-critical. It is then shown that for each \( n \geq 2 \), there is an arbitrarily large dimension-critical graph \( G \) with \( \text{dim}(G) = n \). We close with a few observations and questions that may aid in future work.

Let \( G \) be a simple and finite graph. A graph is said to be decomposed into subgraphs \( H_1 \) and \( H_2 \) which is denoted by \( G = H_1 \oplus H_2 \), if \( G \) is the edge disjoint union of \( H_1 \) and \( H_2 \). If \( G = H_1 \oplus H_2 \oplus \cdots \oplus H_k \), where \( H_1, H_2, \ldots, H_k \) are all isomorphic to \( H \), then \( G \) is said to be \( H \)-decomposable. Furthermore, if \( H \) is a cycle of length \( m \), then we say that \( G \) is \( C_m \)-decomposable and this can be written as \( C_m \mid G \). Where \( G \times H \) denotes the tensor product of graphs \( G \) and \( H \), in this paper, we prove that the necessary conditions for the existence of \( C_6 \)-decomposition of \( K_m \times K_n \) are sufficient. Using these conditions it can be shown that every even regular complete multipartite graph \( G \) is \( C_6 \)-decomposable if the number of edges of \( G \) is divisible by 6.

Let \( F, G \) and \( H \) be graphs. A \( (G, H) \)-decomposition of \( F \) is a partition of the edge set of \( F \) into copies of \( G \) and copies of \( H \) with at least one copy of \( G \) and at least one copy of \( H \). For \( L \subseteq F \), a \( (G, H) \)-packing of \( F \) with leave \( L \) is a \( (G, H) \)-decomposition of \( F – E(L) \). A \( (G, H) \)-packing of \( F \) with the largest cardinality is a maximum \( (G, H) \)-packing. This paper gives the solution of finding the maximum \( (C_k, S_k) \)-packing of the crown \( C_{n, n-1} \).

Rautenbach and Volkmann [Appl. Math. Lett. 20 (2007), 98–102] gave an upper bound for the \( k \)-domination number and \( k \)-tuple domination number of a graph. Hansberg and Volkmann, [Discrete Appl. Math. 157 (2009), 1634–1639] gave upper bounds for the \( k \)-domination number and Roman \( k \)-domination number of a graph. In this note, using the probabilistic method and the known Caro-Wei Theorem on the size of the independence number of a graph, we improve the above bounds on the \( k \)-domination number, the \( k \)-tuple domination number and the Roman \( k \)-domination number in a graph for any integer \( k \geq 1 \). The special case \( k = 1 \) of our bounds improve the known bounds of Arnautov and Payan [V.I. Arnautov, Prikl. Mat. Programm. 11 (1974), 3–8 (in Russian); C. Payan, Cahiers Centre Études Recherche Opér. 17 (1975) 307–317] and Cockayne et al. [Discrete Math. 278 (2004), 11–22].

Addressing a problem posed by Chellali, Haynes, and Hedetniemi (Discrete Appl. Math. 178 (2014) 27–32), we prove \( \gamma_{r2}(G) \leq 2\gamma_r(G) \) for every graph \( G \), where \( \gamma_{r2}(G) \) and \( \gamma_r(G) \) denote the 2-rainbow domination number and the weak Roman domination number of \( G \), respectively. We characterize the extremal graphs for this inequality that are \( \{K_4, K_4 – e\} \)-free, and show that the recognition of the \( K_5 \)-free extremal graphs is NP-hard.

For a graph \( H \), let \( \delta_t(H) = \min\{|\bigcup_{i=1}^t N_H(v_i)| : |v_1, \dots, v_t| \text{ are } t \text{ vertices in } H\} \). We show that for a given number \( \epsilon \) and given integers \( p \geq 2 \) and \( k \in \{2, 3\} \), the family of \( k \)-connected Hamiltonian claw-free graphs \( H \) of sufficiently large order \( n \) with \( \delta(H) \geq 3 \) and \( \delta_k(H) \geq t(n + \epsilon)/p \) has a finite obstruction set in which each member is a \( k \)-edge-connected \( K_3 \)-free graph of order at most \( \max\{p/t + 2t, 3p/t + 2t – 7\} \) and without spanning closed trails. We found the best possible values of \( p \) and \( \epsilon \) for some \( t \geq 2 \) when the obstruction set is empty or has the Petersen graph only. In particular, we prove the following for such graphs \( H \):

• (a) For \( k = 2 \) and a given \( t \) (\( 1 \leq t \leq 4 \)), if \( \delta_t(H) \geq \frac{n+1}{3} \) and \( \delta(H) \geq 3 \), then \( H \) is Hamiltonian.
• (b) For \( k = 3 \) and \( t = 3 \), (i) if \( \delta_3(H) \geq \frac{n+9}{10} \), then \( H \) is Hamiltonian; (ii) if \( \delta_2(H) \geq \frac{n+9}{10} \), then either \( H \) is Hamiltonian, or \( H \) can be characterized by the Petersen graph.
• (c) For \( k = 3 \) and \( t = 3 \), (i) if \( \delta_3(H) \geq \frac{n+9}{8} \), then \( H \) is Hamiltonian; (ii) if \( \delta_3(H) \geq \frac{n+6}{9} \), then either \( H \) is Hamiltonian, or \( H \) can be characterized by the Petersen graph.

These bounds on \( \delta_t(H) \) are sharp. Since the number of graphs of orders at most \( \max\{p/t + 2t, 3p/t + 2t – 7\} \) is finite for given \( p \) and \( t \), improvements to (a), (b), or (c) by increasing the value of \( p \) are possible with the help of a computer.

Any dominating set of vertices in a triangle-free graph can be used to specify a graph coloring with at most one color class more than the number of vertices in the dominating set. This bound is sharp for many graphs. Properties of graphs for which this bound is achieved are presented.