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.

The counting of partitions of a natural number, when they have to satisfy certain restrictions, is done traditionally by using generating functions. We develop a polynomial time algorithm for counting the weighted ideals of partially ordered sets of dimension \(2\). This allows the use of the same algorithm for counting partitions under all sorts of different constraints. In contrast with this, the method is very flexible, and can be used for an extremely large variety of different partitions.

Applying Glauberman’s \(Z^*\)-theorem, it is shown that every finite group \(G\) is strongly \(P_3\)-sequenceable, i.e. there exists a sequencing \((x_1,\ldots,x_{N})\) of the elements of \(G\setminus\{1\}\), such that all products \(x_ix_{i+1}x_{i+2}\) (\(1\leq i\leq N-2\)), \(x_{N-1}x_{N}x_{1}\) and \(x_Nx_{1}x_2\) are nontrivially rewritable. This was conjectured by J. Nielsen in~[N].

Competition graphs were first introduced by Joel Cohen in the study of food webs and have since been extensively studied. Graphs which are the competition graph of a strongly connected or Hamiltonian digraph are of particular interest in applications to communication networks. It has been previously established that every graph without isolated vertices (except \(K_2\)) which is the competition graph of a loopless digraph is also the competition graph of a strongly connected digraph. We establish an analogous result for one generalization of competition graphs, the \(p\)-competition graph. Furthermore, we establish some large classes of graphs, including trees, as the \(p\)-competition graph of a loopless Hamiltonian digraph and show that interval graphs on \(n \geq 4\) vertices are the \(2\)-competition graphs of loopless Hamiltonian digraphs.

Let \(H_n < S_n\), where \(H_n\) is a Sylow \(p\)-subgroup of \(S_n\), the symmetric group on \(n\) letters. Let \(A_n\) denote the number of derangements in \(H_n\), and \(f_n = \frac{h_n}{|H_n|}\). We will show that the sequence \(\{f_n\}_{n=1}^{\infty}\) is dense in the unit interval, but is Cesàro convergent to \(0\).