This paper obtains new combinatorial batch codes (CBCs) from old ones, studies properties of uniform CBCs, and constructs uniform CBCs using semilattices.

For graphs \(F\) and \(H\), where \(H\) has chromatic index \(t\), the proper Ramsey number \(PR(F, H)\) is the smallest positive integer \(n\) such that every \(t\)-edge coloring of \(K_n\) results in a monochromatic \(F\) or a properly colored \(H\). The proper Ramsey number \(PR(F, H)\) is investigated for certain pairs \(F, H\) of connected graphs when \(t = 2\), namely when \(F\) is a complete graph, star, or path and when \(H\) is a path or even cycle of small order. In particular, \(PR(F, H)\) is determined when (1) \(F\) is a complete graph and \(H\) is a path of order 6 or less, (2) \(F\) is a complete graph and \(H\) is a 4-cycle, (3) \(F\) is a star and \(H\) is a 4-cycle or a 6-cycle, and (4) \(F\) is a star and \(H\) is a path of order 8 or less.

The \(k\)-rainbow index \(rx_k(G)\) of a connected graph \(G\) was introduced by Chartrand, Okamoto, and Zhang in 2010. Let \(G\) be a nontrivial connected graph with an edge-coloring \(c: E(G) \to \{1, 2, \ldots, q\}\), \(q \in \mathbb{N}\), where adjacent edges may be colored the same. A tree \(T\) in \(G\) is called a rainbow tree if no two edges of \(T\) receive the same color. For a graph \(G = (V, E)\) and a set \(S \subseteq V\) of at least two vertices, an \(S\)-Steiner tree or a Steiner tree connecting \(S\) (or simply, an \(S\)-tree) is a subgraph \(T = (V’, E’)\) of \(G\) that is a tree with \(S \subseteq V’\). For \(S \subseteq V(G)\) and \(|S| \geq 2\), an \(S\)-Steiner tree \(T\) is said to be a rainbow \(S\)-tree if no two edges of \(T\) receive the same color. The minimum number of colors that are needed in an edge-coloring of \(G\) such that there is a rainbow \(S\)-tree for every \(k\)-set \(S\) of \(V(G)\) is called the \(k\)-rainbow index of \(G\), denoted by \(rx_k(G)\). In this paper, we consider when \(|S| = 3\). An upper bound of complete multipartite graphs is obtained. By this upper bound, for a connected graph \(G\) with \(\text{diam}(G) \geq 3\), we give an upper bound of its complementary graph.

A tree \( T \), in an edge-colored graph \( G \), is called a rainbow tree if no two edges of \( T \) are assigned the same color. For a vertex subset \( S \subseteq V(G) \), a tree that connects \( S \) in \( G \) is called an \( S \)-tree. A \( k \)-rainbow coloring of \( G \) is an edge coloring of \( G \) having the property that for every set \( S \) of \( k \) vertices of \( G \), there exists a rainbow \( S \)-tree \( T \) in \( G \). The minimum number of colors needed in a \( k \)-rainbow coloring of \( G \) is the \( k \)-rainbow index of \( G \), denoted by \( rx_k(G) \). It is NP-hard to compute the \( rx_k(G) \) for the general graphs \( G \). We consider the \( 3 \)-rainbow index of complete bipartite graphs \( K_{s,t} \). For \( 3 \leq s \leq t \), we have determined the tight bounds of \( rx_3(K_{s,t}) \). In this paper, we continue the study. For \( 2 \leq s \leq t \), we develop a converse idea and apply it with the model of chessboard to study the problem. Finally, we obtain the exact value of \( rx_3(K_{s,t}) \) with \( 2 \leq s \leq t \).

The domination polynomials of binary graph operations, aside from union, join and corona, have not been widely studied. We compute and prove recurrence formulae and properties of the domination polynomials of families of graphs obtained by various products, including both explicit formulae and recurrences for specific families.

A graph \( G \) is a homomorphic preimage of another graph \( H \), or equivalently \( G \) is \( H \)-colorable, if there exists a graph homomorphism \( f: G \to H \). A classic problem is to characterize the family of homomorphic preimages of a given graph \( H \). A geometric graph \(\overline{G}\) is a simple graph \( G \) together with a straight line drawing of \( G \) in the plane with the vertices in general position. A geometric homomorphism (resp. isomorphism) \(\overline{G} \to \overline{H}\) is a graph homomorphism (resp. isomorphism) that preserves edge crossings (resp. and non-crossings). The homomorphism poset \(\mathcal{G}\) of a graph \( G \) is the set of isomorphism classes of geometric realizations of \( G \) partially ordered by the existence of injective geometric homomorphisms. A geometric graph \(\overline{G}\) is \(\mathcal{H}\)-colorable if \(\overline{G} \to \overline{H}\) for some \(\overline{H} \in \mathcal{H}\). In this paper, we provide necessary and sufficient conditions for \(\overline{G}\) to be \(C_n\)-colorable for \(3 \leq n \leq 5\).

The mixed discriminant of an \(n\)-tuple of \(n \times n\) matrices \(A_1, \ldots, A_n\) is defined as $$\mathcal{D}(A_1, A_2, \ldots, A_n) = \frac{1}{n!} \sum_{\sigma \in S(n)} \det(A_{\sigma(1)}^{(1)}, A_{\sigma(2)}^{(2)}, \ldots, A_{\sigma(n)}^{(n)}),$$
where \(A^{(i)}\) denotes the \(i\)th column of the matrix \(A\) and \(S(n)\) denotes the group of permutations of \(1, 2, \ldots, n\). For \(n\) matrices \(A_1, \ldots, A_n\) and indeterminates \(\lambda_1, \ldots, \lambda_n\), set $$\Phi_{\lambda_1, \ldots, \lambda_n}(A_1, \ldots, A_n) = \mathcal{D}(\lambda_1 I – A_1, \ldots, \lambda_n I – A_n).$$
It is shown that \(\Phi_{A_1, \ldots, A_n}(A_1, \ldots, A_n) = 0\).

For a graph \(H\) and a positive integer \(\lambda\), let \( ^{\lambda}{H} \) denote the multigraph obtained by replacing each edge of \(H\) with \(\lambda\) parallel edges. Let \(G\) be a multigraph with edge multiplicity \(2\) and with \(C_4\) as its underlying simple graph. We find necessary and sufficient conditions for the existence of a \(G\)-decomposition of \( ^{\lambda}{K_n} \) for all positive integers \(\lambda\) and \(n\).

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.