In this paper, we consider the structure of \(k\)-saturated graphs \((G \not\supset K_k,\) but \(G+e \supset K_{k}\) for all possible edges \(e)\\) having chromatic number at least \(k\).

In this paper, the authors study the vulnerability parameters of integrity, toughness, and binding number for two classes of graphs. These two classes of graphs are permutation graphs of complete graphs and permutation graphs of complete bipartite graphs

In this paper we examine bounds on \(|N(x) \cup N(y)|\) (for nonadjacent pairs \(x,y \in V(G)\)) that imply certain strong Hamiltonian properties in graphs. In particular, we show that if \(G\) is a 2-connected graph of order \(n\) and if for all pairs of distinct nonadjacent vertices \(x, y \in V(G)\),

1. \(|N(z) \cup N(y)| \geq \frac{2n+5}{3}\), then \(G\) is pancyclic.
2. \(|N(z) \cup N(y)| \geq n-t\) and \(\delta(G) \geq t\), then \(G\) is Hamiltonian.
3. \(|N(z) \cup N(y)| \geq n-2\), then \(G\) is vertex pancyclic.

Three types of graphs are investigated with respect to cordiality, namely:graphs which are the complete product of two cordial graphs, graphs which are the subdivision graphs of cordial graphs, cactus graphs.
We give sufficient conditions for the cordiality of graphs of the first two types and show that a cactus graph is cordial if and only if the cardinality of its edge set is not congruent to \(2\) (mod 4).

It is shown that there exists a 4-critical 3-uniform linear hypergraph of order \(m\) for every \(m \geq 56\).

Essentially all pairs of forests \((F_1,F_2)\) are determined for which \(R(F_1,F_2)\) is finite, where \(R(F_1,F_2)\) is the class of minimal Ramsey graphs for the pair \((F_1,F_2)\).

Steiner Heptagon Systems (SHS) of type 1, 2, and 3 are defined and the spectrum of type 2 SHSs (SHS2) is studied. It is shown that the condition \(n \equiv 1 \) { or } \(7 \pmod{14}\) is not only necessary but also sufficient for the existence of an SHS2 of order \(n\), with the possible exceptions of \(n=21\) and \(85\). This gives an interesting algebraic result since the study of SHS2s is equivalent to the study of quasigroups satisfying the identities \(x^2 = x\), \((yx)x = y\), and \((xy)(y(xy)) = (yx)(x(yx))\).

A graph is called well-covered if every maximal independent set has the same size. One generalization of independent sets in graphs is that of a fractional cover – attach nonnegative weights to the vertices and require that for every vertex the sum of all the weights in its closed neighbourhood be at least 1. In this paper, we consider and characterize fractionally well-covered graphs.

We prove that \(e(3,k+1,n) \geq 6n-13k\), where \(e(3,k+1,n)\) is the minimum number of edges in any triangle-free graph on \(n\) vertices with no independent set of size \(k+1\). To achieve this, we first characterize all such graphs with exactly \(e(3,k+1,n)\) edges for \(n \leq 3k\). These results yield some sharp lower bounds for the independence ratio for triangle-free graphs. In particular, the exact value of the minimal independence ratio for graphs with average degree \(4\) is shown to be \(\frac{4}{13}\). A slight improvement to the general upper bound for the classical Ramsey \(R(3,k)\) numbers is also obtained.