Let \(H\) be a subgraph of \(G\). An \(H\)-design \((V, \mathcal{C})\) of order \(v\) and index \(\lambda\) is embedded into a \(G\)-design \((X, \mathcal{B})\) of order \(v+w\), \(w \geq 0\), and index \(\lambda\), if \(\mu \leq \lambda\), \(V \subseteq X\) and there is an injective mapping \(f: \mathcal{C} \rightarrow \mathcal{B}\) such that \(B\) is a subgraph of \(f(B)\) for every \(B \in \mathcal{C}\).
For every pair of positive integers \(v\) and \(\lambda\), we determine the minimum value of \(w\) such that there exists a balanced incomplete block design of order \(v+w\), index \(\lambda \geq 2\) and block-size \(4\) which embeds a \(K_3\)-design of order \(v\) and index \(\mu = 1\).

Let \(S\) be a finite, nonempty set of nonzero integers which contains no squares. We obtain conditions both necessary and sufficient for \(S\) to have the following property: for infinitely many primes \(p\), \(S\) is a set of quadratic nonresidues of \(p\). The conditions are expressed solely in terms of purely external (respectively, internal) combinatorial properties of the set II of all prime factors of odd multiplicity of the elements of \(S\). We also calculate by means of certain purely combinatorial parameters associated with \(\prod\) the density of the set of all primes \(p\) such that \(S\) is a set of quadratic residues of \(p\) and the density of the set of all primes \(p\) such that \(S\) is a set of quadratic nonresidues of \(p\).

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.