We consider edge-colorings of complete graphs in which each color induces a subgraph that does not contain an induced copy of \( K_{1,t} \), for some \( t \geq 3 \). It turns out that such colorings, if the underlying graph is sufficiently large, contain spanning monochromatic \( k \)-connected subgraphs. Furthermore, there exists a color, say blue, such that every vertex has very few incident edges in colors other than blue.

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

For graphs \(G\) and \(H\), Ramsey number \(R(G, H)\) is the smallest natural number \(n\) such that no \((G, H)\)-free graph on \(n\) vertices exists. In 1981, Burr [5] proved the general lower bound \(R(G, H) \geq (n – 1)(\chi(H) – 1) + \sigma(H)\), where \(G\) is a connected graph of order \(n\), \(\chi(H)\) denotes the chromatic number of \(H\) and \(\sigma(H)\) is its chromatic surplus, namely, the minimum cardinality of a color class taken over all proper colorings of \(H\) with \(\chi(H)\) colors. A connected graph \(G\) of order \(n\) is called good with respect to \(H\), \(H\)-good, if \(R(G, H) = (n – 1)(\chi(H) – 1) + \sigma(H)\). The notation \(tK_m\) represents a graph with \(t\) identical copies of complete graph \(K_m\). In this note, we discuss the goodness of cycle \(C_n\) with respect to \(tK_m\) for \(m, t \geq 2\) and sufficiently large \(n\). Furthermore, it is also provided the Ramsey number \(R(G, tK_m)\), where \(G\) is a disjoint union of cycles.

If \(T\) is a tree on \(n\) vertices, \(n \geq 3\), and if \(G\) is a connected graph such that \(d(u) + d(v) + d(u,v) \geq 2n\) for every pair of distinct vertices of \(G\), it has been conjectured that \(G\) must have a non-separating copy of \(T\). In this note, we prove this result for the special case in which \(d(u) + d(v) + d(u,v) \geq 2n + 2\) for every pair of distinct vertices of \(G\), and improve this slightly for trees of diameter at least four and for some trees of diameter three.

Let \(G\) be a finite simple group, \(M\) be a maximal subgroup of \(G\) and \(C_g = nX\) be the conjugacy class of \(G\) containing \(g\). In this paper we discuss a new method for constructing \(1-(v,k,\lambda)\) designs \(\mathcal{D} = (\mathcal{P},\mathcal{B})\), where \(\mathcal{P} = nX\) and \(\mathcal{B} = \{(M\cap nX)^y \mid y \in G\}\). The parameters \(v\), \(k\), \(\lambda\) and further properties of \(\mathcal{D}\) are determined. We also study codes associated with these designs.

Let \(G\) be a graph and \(H\) a subgraph of \(G\). A \(D(G, H, \lambda)\) design is a collection \(\mathcal{D}\) of subgraphs of \(G\) each isomorphic to \(H\) so that every \(2\)-path (path of length \(2\)) in \(G\) lies in exactly \(\lambda\) subgraphs in \(\mathcal{D}\). The problem of constructing \(D(K_n,C_n,1)\) designs is the so-called Dudeney’s round table problem. We denote by \(C_k\), a cycle on \(k\) vertices and by \(P_k\), a path on \(k\) vertices.

In this paper, we construct \(D(K_{n,n},C_{2n},1)\) designs and \(D(K_n,P_n,1)\) designs when \(n \equiv 0,1,3 \pmod{4}\); and \(D(K_{n,n},C_{2n},2)\) designs and \(D(K_n,P_n,2)\) designs when \(n \equiv 2 \pmod{4}\). The existence problems of \(D(K_{n,n},C_{2n},1)\) designs and \(D(K_n,P_n,1)\) designs for \(n \equiv 2 \pmod{4}\) remain open.

The spread of a graph \(G\) is defined as the difference between the largest and smallest eigenvalues of \(G\). Using the lower bounds obtained by Liu and Liu in [4] on the spread of a graph, we in this note present spread conditions for some Hamiltonian properties of a graph.

A \({vertex \;cover}\) of a graph \(G = (V, E)\) is a subset \(S \subseteq V\) such that every edge is incident with at least one vertex in \(S\), and \(\alpha(G)\) is the cardinality of a smallest vertex cover. For a given vertex cover \(S\), a defense by \(S\) to an attack on an edge \(e = \{v, w\}\), where \(v \in S\), is a one-to-one function \(f : S \to V\), such that:

1. \(f(v) = w\), and
2. for each \(s \in S – v\), \(f(s) \in N[s]\).

Informally, a set is an \({eternal\; vertex \;cover}\) if it can defend an “attack” on any edge and the process can be repeated indefinitely. The cardinality of a smallest eternal vertex cover is denoted \(\alpha_{m}^\infty(G)\). A set of vertices which is not an eternal vertex cover is \({mortal}\). A formal definition of eternal vertex cover is provided and demonstrated to be equivalent to a characterization using closed families of vertex covers.
Eternal vertex covers are shown to be closed under taking supersets and a lower bound for \(\alpha_{m}^\infty(G)\) is given which depends on the vertex connectivity number and the independent domination number. A corresponding upper bound is given for the size of a mortal set. The \({death \;spiral\; number}\) of a mortal vertex cover is defined and used to partition the collection of all mortal sets. Mortal sets are shown to be closed under taking subsets implying the collection of mortal sets for a graph with at least one edge is an independence system. The death spiral number of a graph is the maximum of the death spiral numbers of all mortal sets.
An optimal attack/defense strategy is determined for a set of size \(\alpha_{m}^\infty(T) – 1\) in a tree \(T\), along with a polynomial labeling algorithm which computes its death spiral number.

We first introduce the concept of \((k, k’, k”)\)-domination numbers in graphs, which is a generalization of many domination parameters. Then we find lower and upper bounds for this parameter, which improve many well-known results in the literature.

We are interested in ordering the elements of a subset \( A \) of the non-zero integers modulo \( n \) in such a way that all the partial sums are distinct. We conjecture that this can always be done, and we prove various partial results about this problem.