A DI-pathological graph is a graph in which every minimum dominating set intersects every maximal independent set. DI-pathological graphs are related to the Inverse Domination Conjecture; hence, it is useful to characterize properties of them. One characterization question is how large or small a graph can be relative to the domination number. Two useful characterizations of size seem relevant, namely the number of vertices and the number of edges. In this paper, we provide two results related to this question. In terms of the number of vertices, we show that every connected, DI-pathological graph has at least \(2\gamma(G) + 4\) vertices except \(K_{3,3}\), \(K_{3,4}\), and six graphs on nine vertices and show that our lower bound is best possible. We then show that with one exception, every connected, DI-pathological graph with no isolated vertices has at least \(2\gamma(G) + 5\) edges and show that our lower bound is best possible.

A dominating set in a graph \( G \) is a subset \( S \) of vertices such that any vertex not in \( S \) is adjacent to some vertex of \( S \). The domination number, \( \gamma(G) \), of \( G \) is the minimum cardinality of a dominating set. A dominating set of cardinality \( \gamma(G) \) is called a \( \gamma(G) \)-set. A fair dominating set in a graph \( G \) (or FD-set) is a dominating set \( S \) such that all vertices not in \( S \) are dominated by the same number of vertices from \( S \); that is, every two vertices not in \( S \) have the same number of neighbors in \( S \). The fair domination number, \( fd(G) \), of \( G \) is the minimum cardinality of an FD-set. A fair dominating set of \( G \) of cardinality \( fd(G) \) is called an \( fd(G) \)-set. We say that \( fd(G) \) and \( \gamma(G) \) are \emph{strongly equal} and denote by \( fd(G) \equiv \gamma(G) \), if every \( \gamma(G) \)-set is an \( fd(G) \)-set. In this paper, we provide a constructive characterization of trees \( T \) with \( fd(T) \equiv \gamma(T) \).

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 \emph{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 \emph{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 \emph{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 \emph{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.