It is known that each incidence matrix between any two levels of the Boolean lattice and the lattice of flats of a finite projective geometry has full rank. We show that this also holds for the lattice of flats of a finite affine geometry.

In this paper, we prove that if \(G\) is a \(k\)-connected (\(k \geq 2\)) graph of order \(n\) such that the sum of degrees of any \(k+1\) independent vertices is at least \(n+k\), and if the set of claw centers of \(G\) is independent, then \(G\) is hamiltonian.

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.

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\).

Let \(B(G)\) and \(B_c(G)\) denote the bandwidth and cyclic bandwidth of graph \(G\), respectively. In this paper, we shall give a sufficient condition for graphs to have equal bandwidth and cyclic bandwidth. This condition is satisfied by trees. Thus all theorems on bandwidth of graphs apply to cyclic bandwidth of graphs satisfying the sufficiency condition, and in particular, to trees. We shall also give a lower bound of \(B_c(G)\) in terms of \(B(G)\).

A \((n,5)\)-cage is a minimal graph of regular degree \(n\) and girth \(5\). Let \(f(n,5)\) denote the number of vertices in a \((n,5)\)-cage. The best known example of an \((n,5)\)-cage is the Petersen graph, the \((3,5)\)-cage. The \((4,5)\)-cage is the Robertson graph, the \((7,5)\)-cage is the Hoffman-Singleton graph, the \((6,5)\)-cage was found by O’Keefe and Wong~[2] and there are three known \((5,5)\)-cages. No other \((n,5)\)-cages are known for \(n \geq 8\). In this paper, we will use a graph structure called remote edges and a set of mutually orthogonal Latin squares to give an upper bound of \(f(n,5)\) for \(n = 2^k+1\).

Let \(S\) be a set of graphs on which a measure of distance (a metric) has been defined. The distance graph \(D(S)\) of \(S\) is that graph with vertex set \(S\) such that two vertices \(G\) and \(H\) are adjacent if and only if the distance between \(G\) and \(H\) (according to this metric) is \(1\). A basic question is the determination of which graphs are distance graphs. We investigate this question in the case of a metric which we call the switching distance. The question is answered in the affirmative for a number of classes of graphs, including trees and all cycles of length at least \(4\). We establish that the union and Cartesian product of two switching distance graphs are switching distance graphs. We show that each of \(K_3\), \(K_{2,4}\) and \(K_{3,3}\) is not a switching distance graph.

A set \(\mathcal{P} \subseteq V(G)\) is a \(k\)-packing of a graph \(G\) if for every pair of vertices \(u,v \in P\), \(d(u,v) \geq k+1\). We define a graph \(G\) to be \(k\)-equipackable if every maximal \(k\)-packing of \(G\) has the same size. In this paper, we construct, for \(k \leq 1\), an infinite family \(\mathcal{F}_k\) of \(k\)-equipackable graphs, recognizable in polynomial time. We prove further that for graphs of girth at least \(4k+4\), every \(k\)-equipackable graph is a member of \(\mathcal{F}_k\).

An \(m \times n\) ideal matrix is a \(3\)-periodic \(m \times n\) binary matrix which satisfies the following two conditions: (1) each column of this matrix contains precisely one \(1\) and (2) if it is visualized as a dot pattern (with each dot representing a \(1\)), then the number of overlapping dots at all actual shifts are \(1\) or \(0\). Let \(s(n)\) denote the smallest integer \(m\) such that an \(m \times n\) ideal matrix exists. In this paper, we reduce the upper bound of \(s(n)\) which was found by Fung, Siu and Ma. Also, we list an upper bound of \(s(n)\) for \(14 \leq n \leq 100\).

I. Several unbiased tournament schedules for round robin doubles tennis are presented, in a form which can be useful to the urban league tournament director. The unbiased tournament affords less restriction than does the usual spouse-avoiding tournament (see~[{7}]). As gender considerations are not necessary, it is most often the tournament of choice.

In this note, we give a method to construct binary self-dual codes using weighing matrices. By this method, we construct extremal self-dual codes obtained from weighing matrices. In particular, the extended Golay code and new extremal singly-even codes of length \(40\) are constructed from certain weighing matrices. We also get necessary conditions for the existence of some weighing matrices.

Symmetric balanced squares for different sizes of array and for different numbers of treatments have been constructed. An algorithm, easily implementable on computers, has been developed for construction of such squares whenever the parameters satisfy the necessary conditions for existence of the square. The method of construction employs \(1\)-factorizations of a complete graph or near \(1\)-factorizations of a complete graph, depending on whether the size of the array is even or odd, respectively. For odd sized squares the method provides a solution directly based on the near \(1\)-factorization. In the case of the squares being of even size, we use Hall’s matching theorem along with a \(1\)-factorization if \([\frac{n^2}{v}]\) is even, otherwise, Hall’s matching theorem together with Fulkerson’s~\([4]\) theorem, on the existence of a feasible flow in a network with bounds on flow leaving the sources and entering the sinks, lead to the required solution.

This paper presents a probabilistic polynomial-time reduction of the discrete logarithm problem in the general linear group \(\mathrm{GL}(n, \mathbb{F})\) to the discrete logarithm problem in some small extension fields of \(\mathbb{F}_p\).

A distance two labelling (or coloring) is a vertex labelling with constraints on vertices within distance two, while the regular vertex coloring only has constraints on adjacent vertices (i.e. distance one). In this article, we consider three different types of distance two labellings. For each type, the minimum span, which is the minimum range of colors used, will be explored. Upper and lower bounds are obtained. Graphs that attain those bounds will be demonstrated. The relations among the minimum spans of these three types are studied.

Arcs and linear maximum distance separable \((M.D.S.)\) codes are equivalent objects~\([25]\). Hence, all results on arcs can be expressed in terms of linear M.D.S. codes and conversely. The list of all complete \(k\)-arcs in \(\mathrm{PG}(2,q)\) has been previously determined for \(q \leq 16\). In this paper, (i) all values of \(k\) for which there exists a complete \(k\)-arc in \(\mathrm{PG}(2,q)\), with \(17 \leq q \leq 23\), are determined; (ii) a complete \(k\)-arc for each such possible \(k\) is exhibited.

An \((r,s; m,n)\)-de Bruijn array is a periodic \(r \times s\) binary array in which each of the different \(m \times n\) matrices appears exactly once. C.T. Fan, S.M. Fan, S.L. Ma and M.K. Siu established a method to obtain either an \((r,2^n;m+1,n)\)-array or a \((2r,2^{n-1};m+1,n)\)-array from an \((r,s; m, n)\)-array. A class of square arrays are constructed by their method. In this paper, decoding algorithms for such arrays are described.