For positive integers \(t\) and \(k\), the \({vertex}\) (resp. edge) Folkman number \(F_v(t,t,t;k)\) (resp. \(F_e(t,t,t;k)\)) is the smallest integer \(n\) such that there is a \(K_k\)-free graph of order \(n\) for which any three coloring of its vertices (resp. edges) yields a monochromatic copy of \(K_t\). In this note, an algorithm for testing \((t,t,\ldots,t;k)\) in cyclic graphs is presented and it is applied to find new upper bounds for some vertex or edge Folkman numbers. By using this method, we obtain \(F_v(3,3,3;4) \leq 66\), \(F_v(3,3,3;5) \leq 24\), which leads to \(F_v(6,6,6;7) \leq 726\), and \(F_v(3,3,3;8) \leq 727\).

As usual, \(K_{m,n}\) denotes the complete bipartite graph with parts of sizes \(m\) and \(n\). For positive integers \(k \leq n\), the crown \(C_{n,k}\) is the graph with vertex set \(\{a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}\}\) and edge set \(\{a_ib_j: 0 \leq i \leq n-1, j = i,i+1, \ldots, i+k-1 \pmod{n}\}\). A spider is a tree with at most one vertex of degree more than two, called the \({center}\) of the spider. A leg of a spider is a path from the center to a vertex of degree one. Let \(S_l(t)\) denote a spider of \(l\) legs, each of length \(t\). An \(H\)-decomposition of a graph \(G\) is an edge-disjoint decomposition of \(G\) into copies of \(H\). In this paper, we investigate the problems of \(S_l(2)\)-decompositions of complete bipartite graphs and crowns, and prove that: (1) \(K_{n,tl}\) has an \(S_l(2)\)-decomposition if and only if \(nt \equiv 0 \pmod{2}\), \(n \geq 2l\) if \(t = 1\), and \(n \geq 1\) if \(t \geq 2\), (2) for \(t \geq 2\) and \(n \geq tl\), \(C_{n,tl}\) has an \(S_l(2)\)-decomposition if and only if \(nt \equiv 0 \pmod{2}\), and (3) for \(n \geq 3t\), \(C_{n,tl}\) has an \(S_3(2)\)-decomposition if and only if \(nt \equiv 0 \pmod{2}\) and \(n \equiv 0 \pmod{4}\) if \(t = 1\).

In this paper, we extend the study on packing complete graphs \(K_v\) with \(6\)-cycles. Mainly, we obtain the maximum packing of \(K_v – L\) and a leave, where \(L\) is a vertex-disjoint union of cycles in \(K_v\).

For a vertex \(v\) of a graph \(G\), the unlabeled subgraph \(G-v\) is called a \({card}\) of \(G\). We prove that the connectedness of an \(n\)-vertex graph \(G\) and the presence of isolated vertices in \(G\) can be determined from any collection of \(n-2\) of its cards. It is also proved that if two graphs on \(n \geq 6\) vertices with minimum degree at least two have \(n-2\) cards in common, then the numbers of edges in them differ by at most one.

Let \(G\) be a connected cubic graph embedded on a surface \(\Sigma\) such that every face is bounded by a cycle of length \(6\). By Euler formula, \(\Sigma\) is either the torus or the Klein bottle. The corresponding graphs are called toroidal polyhex graphs and Klein-bottle polyhex graphs, respectively. It was proved that every toroidal polyhex graph is hamiltonian. In this paper, we prove that every Klein-bottle polyhex graph is hamiltonian. Furthermore, lower bounds for the number of Hamilton cycles in Klein-bottle polyhex graphs are obtained.

The matching preclusion number of a graph \(G\), denoted by \(mp(G)\), is the minimum number of edges whose deletion leaves a resulting graph that has neither perfect matchings nor almost perfect matchings. Besides its theoretical linkage with conditional connectivity and extremal graph theory, the matching preclusion number serves as a measure of robustness in interconnection networks. In this paper, we develop general properties related to matchings in the Cartesian product of graphs, enabling us to establish the matching preclusion number for various interconnection (product) networks, specifically: hyper Petersen, folded Petersen, folded Petersen cube, hyperstar, star-cube, and hypercube. Furthermore, we show that the Cartesian product of graphs operation inherits the matching preclusion number optimality from factor graphs of even order, reinforcing the Cartesian product as a desirable network-synthesizing operator.

This paper proves that the graphic matroids with at least two edges and no isolated vertices coincide with the class of complete \(k\)-partite graphs, where, when \(k \leq 3\), no partition class has size one. It also shows that a simple rank-\(r\) binary matroid \(M\) has every two elements in a \(4\)-circuit if \(|E(M)| \geq 2^{r-1} + 2\).

Multi-sender authentication codes allow a group of senders to construct an authenticated message for a receiver such that the receiver can verify authenticity of the received message. In this paper, we constructed one multi-sender authentication codes from pseudo-symplectic geometry over finite fields. The parameters and the probabilities of deceptions of this codes are also computed.

Let \(G\) be a graph with vertex set \(V\). A set \(D \subseteq V\) is a total restrained dominating set of \(G\) if every vertex in \(V\) has a neighbor in \(D\) and every vertex in \(V-D\) has a neighbor in \(V-D\). The minimum cardinality of a total restrained dominating set of \(G\) is called the total restrained domination number of \(G\), denoted by \(\gamma_{tr}(G)\). Cyman and Raczek \((2006)\) showed that if \(G\) is a connected graph of order \(n\) and minimum degree \(\delta\) such that \(2 \leq \delta \leq n-2\), then \(\gamma_{tr}(G) \leq n-\delta\). In this paper, we first introduce the concept of max-min total restrained domination number, denoted by \(\gamma_{tr}^M(G)\), of \(G\), and extend the above result by showing that \(\gamma_{tr}^M(G) \leq \gamma_{tr}(G) \leq n-\delta\). We then proceed to establish that \((1)\) \(\gamma_{tr}^M(G) \leq n-2\delta\) if \(n \geq 11\) and \(G\) contains a cut-vertex, and \((2)\) \(\gamma_{tr}(G) \leq n-4\) if \(n \geq 11\) and \(\delta \geq 2\).

In response surface analysis, it is generally assumed that the observations are independent and there is no effect of neighbouring units. But under the situation when the units are placed linearly with no gaps, the experimental units may experience neighbour or overlap effects from neighbouring units. Hence, for proper specification it is important to include the neighbour effects in the model. First order response surface mode! with neighbour effects from immediate left and right neighbouring units has been considered here and the conditions have been derived for the orthogonal estimation of coefficients of this model. The variance of estimated response has also been obtained and conditions for first order response surface model with neighbour effects to be rotatable have been obtained. A method of obtaining designs satisfying the derived conditions has been proposed. A first order rotatable design with neighbour effects using half replicate of \(2^3\) has also been given.