A graph without \(4\)-cycles is called \(C_4\)-free. A \(C_4\)-free graph is \(C_4\)-saturated if adding any edge creates a 4-cycle. Ollmann showed that any \(n\)-node \(C_4\)-saturated graph has at least \(\frac{3}{2}n – 3\) edges. He also described the set of all \(n\)-node \(C_4\)-saturated graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges. A graph is \(P_3\)-connected if each pair of nonadjacent nodes is connected by a path with exactly \(3\) edges. A \(C_4\)-saturated graph is \(P_3\)-connected, but not vice versa. We generalize Ollmann’s results by proving that any \(n\)-node \(P_3\)-connected graph has at least \(\frac{3}{2}n – 3\) edges. We also describe the set of all \(n\)-node \(P_3\)-connected graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges. This is a superset of Ollmann’s set as some \(n\)-node \(P_3\)-connected graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges do have \(4\)-cycles.

For a given graph \(G\) an edge-coloring of \(G\) with colors \(1,2,3,\ldots\) is said to be a \emph{consecutive coloring} if the colors of edges incident with each vertex are distinct and form an interval of integers. In the case of bipartite graphs this kind of coloring has a number of applications in scheduling theory. In this paper we investigate the question whether a bipartite graph has a consecutive coloring with \(\Delta\) colors. We show that the above question can be answered in polynomial time for \(\Delta \leq 4\) and becomes NP-complete if \(\Delta > 4\).

In this article we give a direct construction of \(HPMD\). As an application, we discuss the existence of \((v,6,1)\)-\(PMD\) and obtain an infinite class of \((v,6,1)\)-\(PMD\) where \(v \equiv 4 \pmod{6}\).

A graph is \({{well \; covered}}\) if every maximal independent set has the same size and \({very \;well\; covered}\) if every maximal independent set contains exactly half the number of vertices. In this paper, we present an alternative characterization of a certain sub-class of well-covered graphs and show that this generalizes a characterization of very well covered graphs given by Favaron [3].

We call a node of a simple graph \({connectivity\;-redundant}\) if its removal does not diminish the connectivity. Studying the distribution of such nodes in a CKL-graph, i.e., a connected graph \(G\) of order \(\geq 3\) whose connectivity \(\kappa\) and minimum degree \(\delta\) satisfy the inequality \(\kappa \geq (\frac{3\kappa – 1}{2})\), we obtain a best lower bound, sharp for any \(\kappa > 1\), for the number of connectivity-redundant nodes in \(G\), which is \(\kappa + 1\) or \(\kappa + 2\) according to whether \(\kappa\) is odd or even, respectively. As a by-product we obtain a new proof of an old theorem of Watkins concerning node-transitive graphs.

Let \(T = (V,A)\) be a digraph with \(n\) vertices. \(T\) is called a local tournament if for every vertex \(x \in V\), \(T[O(x)]\) and \(T[I(x)]\) are tournaments. In this paper, we prove that every arc-cyclic connected local tournament \(T\) is arc-pancyclic except \(T\cong T_{6}-,T_{8}\)-type digraphs or \(D_8\).

Results concerning the enumeration and classification of \(7\times7\) Latin squares are used to enumerate and classify all non-isomorphic Youden squares of order \(6\times7\). We show that the number of non-isomorphic Youden squares obtainable from a species of Latin square Latin Square \({\delta}\), depends on the number of distinct adjugate sets and the order of the automorphism group of Latin Square\({\delta}\). Further, we use the results obtained for \(6\times7\) Youden squares as a basis for the enumeration and classification of \(6\times7\) DYRs.

The spectra of \(5\)-, \(7\)-, and \(11\)-rotational Steiner triple systems are determined. In the process, existence for a number of generalized Skolem sequences is settled.

Given an undirected graph \(G\) and four distinct special vertices \(s_1,s_2,t_1,t_2\), the Undirected Two Disjoint Paths Problem consists in determining whether there are two disjoint paths connecting \(s_1\) to \(t_1\) and \(s_2\) to \(t_2\), respectively.

There is an analogous version of the problem for acyclic directed graphs, in which it is required that the two paths be directed, as well.

The well-known characterizations for the nonexistence of solutions in both problems are, in some sense, the same, which indicates that under some weak conditions the edge orientations in the directed version are irrelevant. We present the first direct proof of the irrelevance of edge orientations.

Let \(G\) be a connected claw-free graph, \(M(G)\) the set of all vertices of \(G\) that have a connected neighborhood, and \((M(G))\) the induced subgraph of \(G\) on \(M(G)\). We prove that:

1. if \(M(G)\) dominates \(G\) and \(\langle M(G)\rangle \) is connected, then \(G\) is vertex pancyclic orderable,
2. if \(M(G)\) dominates \(G\), \(\langle M(G)\rangle\) is connected, and \(G\setminus M(G)\) is triangle-free, then \(G\) is fully \(2\)-chord extendible,
3. if \(M(G)\) dominates \(G\) and the number of components of \(\langle M(G)\rangle\) does not exceed the connectivity of \(G\), then \(G\) is hamiltonian.