A Latin square is $N_e$ if it has no intercalates (Latin subsquares of order $2$). We correct results published in an earlier paper by McLeish, dealing with a construction for $N_2$ Latin squares.

In [13], we conjectured that if $G=(V_1,V_2;E)$ is a bipartite graph with $|V_1|=|V_2|=2k$ and minimum degree at least $k+1$, then $G$ contains $k$ vertex-disjoint quadrilaterals. In this paper, we propose a more general conjecture: If $G=(V_1,V_2;E)$ is a bipartite graph such that $|V_1|=|V_2|=n\ge 2$ and $\delta (G)\ge [n/2]+1$, then for any bipartite graph $H=(U_1,U_2;F)$ with $|U_1|\le n,|U_2|\le n$ and $\mathrm{\Delta }(H)\le 2,G$ contains a subgraph isomorphic to $H$. To support this conjecture, we prove that if $n=2k+t$ with $k\ge 0$ and $t\ge 3,G$ contains $k+1$ vertex-disjoint cycles covering all the vertices of $G$ such that $k$ of them are quadrilaterals.

In a finite projective plane, a $k$-arc $\mathcal{K}$ covers a line $l_0$ if every point on $l_0$ lies on a secant of $\mathcal{K}$. Such $k$-arcs arise from determining sets of elements for which no linear $(n,q,t)$-perfect hash families exist [1], as well as from finding sets of points in $\mathrm{A}\mathrm{G}(2,q)$ which determine all directions [2]. This paper provides a lower bound on $k$ and establishes exactly when the lower bound is attained. This paper also gives constructions of such $k$-arcs with $k$ close to the lower bound.

In this paper we determine the $k$-domination number ${\gamma }_k$ of $P_{2k+2}\times P_n$ and $\underset{m,n\to \mathrm{\infty }}{lim}\frac{{\mathrm{\Gamma }}_k(P_m\times P_n)}{mn}$.

A digraph obtained by replacing each edge of a complete $n$-partite graph by an arc or a pair of mutually opposite arcs is called a semi-complete $n$-partite digraph. An $n$-partite tournament is an orientation of a complete $n$-partite graph. In this paper we shall prove that a strongly connected semicomplete $n$-partite digraph with a longest directed cycle $C$, contains a spanning strongly connected $n$-partite tournament which also has the longest directed cycle $C$ with exception of a well determined family of semicomplete bipartite digraphs. This theorem shows that many well-known results on strongly connected $n$-partite tournaments are also valid for strongly connected semicomplete $n$-partite digraphs.

Let $k$ be a positive integer and let $G$ be a graph. For two distinct vertices $x,y\in V(G)$, the $k$-wide-distance $d_k(x,y)$ between $x$ and $y$ is the minimum integer $l$ such that there exist $k$ vertex-disjoint $(x,y)$-paths whose lengths are at most $l$. We define $d_k(x,x)=0$. The $k$-wide-diameter $d_k(G)$ of $G$ is the maximum value of the $k$-wide-distance between two vertices of $G$. In this paper we show that if $G$ is a graph with $d_k(G)\ge 2$ ($k\ge 3$), then there exists a cycle which contains specified $k$ vertices and has length at most $2(k–3)({\mathrm{d}}_{\mathrm{k}}(G)–1)+max\{3d_k(G),\lfloor \frac{18d_k(G)-16}{5}\rfloor \}$.

Let $G_1$ and $G_2$ be two graphs of the same size such that $V(G_1)=V(G_2)$, and let $H$ be a connected graph of order at least $3$. The graphs $G_1$ and $G_2$ are $H$-adjacent if $G_1$ and $G_2$ contain copies $H_1$ and $H_2$ of $H$, respectively, such that $H_1$ and $H_2$ share some but not all edges and $G_2=G_1–E(H_1)+E(H_2)$. The graphs $G_1$ and $G_2$ are $H$-connected if $G_1$ can be obtained from $G_2$ by a sequence of $H$-adjacencies. The relation $H$-connectedness is an equivalence relation on the set of all graphs of a fixed order and fixed size. The resulting equivalence classes are investigated for various choices of the graph $H$.

A generalized $p$-cycle is a digraph whose set of vertices is partitioned in $p$ parts that are cyclically ordered in such a way that the vertices in one part are adjacent only to vertices in the next part. In this work, we mainly show the two following types of conditions in order to find generalized $p$-cycles with maximum connectivity:

1. For a new given parameter $ϵ$, related to the number of short paths in $G$, the diameter is small enough.

2. Given the diameter and the maximum degree, the number of vertices is large enough.

For the first problem it is shown that if $D\le 2\ell +p–2$, then the connectivity is maximum. Similarly, if $D\le 2\ell +p–1$, then the edge-connectivity is also maximum. For problem two an appropriate lower bound on the order, in terms of the maximum and minimum degree, the parameter $\ell$ and the diameter is deduced to guarantee maximum connectivity.

For a graph $G=(V,E)$ and $X\subseteq V(G)$, let ${\mathrm{dist}}_G(u,v)$ be the distance between the vertices $u$ and $v$ in $G$ and ${\sigma }_3(X)$ denote the minimum value of the degree sum (in $G$) of any three pairwise non-adjacent vertices of $X$. We obtain the main result: If $G$ is a $1$-tough graph of order $n$ and $X\subseteq V(G)$ such that ${\sigma }_3(X)\ge n$ and, for all $x,y\in X$, ${\mathrm{dist}}_G(x,y)=2$ implies $max\{d(x),d(y)\}\ge \frac{n-4}{2}$, then $G$ has a cycle $C$ containing all vertices of $X$. This result generalizes a result of Bauer, Broersma, and Veldiman.

Some constructions of affine $({\alpha }_1,\dots ,{\alpha }_n)$-resolvable $(r,\lambda )$-designs are discussed, by use of affine $\alpha$-resolvable balanced incomplete block designs or semi-regular group divisible designs. A structural property is also indicated.

We establish a connection between the principle of inclusion-exclusion and the union-closed sets conjecture. In particular, it is shown that every counterexample to the union-closed sets conjecture must satisfy an improved inclusion-exclusion identity.

Broadcasting in a network is the process whereby information, initially held by one node, is disseminated to all nodes in the network. It is assumed that, in each unit of time, every vertex that has the information can send it to at most one of its neighbours that does not yet have the information. Furthermore, the networks considered here are of bounded (maximum) degree $\mathrm{\Delta }$, meaning that each node has at most $\mathrm{\Delta }$ neighbours. In this article, a new parameter, the average broadcast time, defined as the minimum mean time at which a node in the network first receives the information, is introduced. It is found that when the broadcast time is much greater than the maximum degree, the average broadcast time is (approximately) between one and two time units less than the total broadcast time if the maximum degree is at least three.

The path spectrum, $\mathrm{sp}(G)$, of a graph $G$ is the set of all lengths of maximal paths in $G$. The path spectrum is continuous if $\mathrm{sp}(G)=\{\ell ,\ell 1,\dots ,\ell \}$ for some $\ell \le m$. A graph whose path spectrum consists of a single element is called scent and is by definition continuous. In this paper, we determine when a $\{K_{1,3},S\}$-free graph has a continuous path spectrum where $S$ is one of $C_3,P_4,P_5,P_6,Z_1,Z_2,Z_3,N,B$, or $W$.

A graph $G$ is $(p,q,r)$-choosable if for every list assignment $L$ with $|L(v)|\ge p$ for each $v\in V(G)$ and $|L(u)\cap L(v)|<p–r$ whenever $u,v$ are adjacent vertices, $G$ is $q$-tuple $L$-colorable. We give an alternative proof of $(4t,t,3t)$-choosability for the planar graphs and construct a triangle-free planar graph on $119$ vertices which is not $(3,1,1)$-choosable (and so neither $3$-choosable). We also propose some problems.

We study the behaviour of two domination parameters: the split domination number ${\gamma }_s(G)$ of a graph $G$ and the maximal domination number ${\gamma }_m(G)$ of $G$ after the deletion of an edge from $G$. The motivation of these problems comes from [2]. In [6] Vizing gave an upper bound for the size of a graph with a given domination number. Inspired by [5] we formulate Vizing type relation between $|E(G)|,|V(G)|,\mathrm{\Delta }(G)$ and $\delta (G)$, where $\mathrm{\Delta }(G)$ ($\delta (G)$) denotes the maximum (minimum) degree of $G$.

A $2$-factor $F$ of a bipartite graph $G=(A,B;E)$, $|A|=|B|=n$, is small if $F$ comprises $\lfloor \frac{n}{2}\rfloor$ cycles. A set $\mathfrak{F}$ of small edge-disjoint $2$-factors of $G$ is maximal if $G–\mathfrak{F}$ does not contain a small $2$-factor. We study the spectrum of maximal sets of small $2$-factors.

The linear vertex-arboricity of a graph $G$ is defined as the minimum number of subsets into which the vertex-set $V(G)$ can be partitioned so that every subset induces a linear forest. In this paper, we give the upper and lower bounds for the sum and product of linear vertex-arboricity with independence number and with clique cover number, respectively. All of these bounds are sharp.

The independence polynomial of graph $G$ is the function $i(G,x)=\sum i_k{x}^k$, where $i_k$ is the number of independent sets of cardinality $k$ in $G$. We ask the following question: for fixed independence number $\beta$, how large can the modulus of a root of $i(G,x)$ be, as a function of $n$, the number of vertices? We show that the answer is $(\frac{n}{\beta }{)}^{\beta –1}+O(n^{S-2})$.

Balance has played an important role in the study of random graphs and matroids. A graph is balanced if its average degree is at least as large as the average degree of any of its subgraphs. The density of a non-empty loopless matroid is the number of elements of the matroid divided by its rank. A matroid is balanced if its density is at least as large as the density of any of its submatroids. Veerapadiyan and Arumugan obtained a characterization of balanced graphs; we extend their result to give a characterization of balanced matroids.

We show that there is a straight line embedding of the complete graph $K_C$ into ${\mathcal{R}}^3$ which is space-filling: every point of ${\mathcal{R}}^3$ is either one of the vertices of $K_C$, or lies on exactly one straight line segment joining two of the vertices.

An efficient algorithm for computing chromatic polynomials of graphs is presented. To make very large computations feasible, the algorithm combines the dynamic modification of a computation tree with a hash table to store information from isomorphically distinct graphs that occur during execution. The idea of a threshold facilitates identifying graphs that are isomorphic to previously processed graphs. The hash table together with thresholds allow a table look-up procedure to be used to terminate some branches of the computation tree. This table lookup process allows termination of a branch of the computation tree whenever the graph at a node is isomorphic to a graph that is stored in the hash table. The hashing process generates a large file of graphs that can be used to find any chromatically equivalent graphs that were generated. The initial members of a new family of chromatically equivalent graphs were discovered using this algorithm.

In this paper, we investigate the sufficient conditions for a graph to contain a cycle (path) $C$ such that $G$ – $V(C)$ is a disjoint union of cliques. In particular, sufficient conditions involving degree sum and neighborhood union are obtained.

Let $k$ and $d$ be integers with $d\ge k\ge 4$, let $G$ be a $k$-connected graph with $|V(G)|\ge 2d–1$, and let $x$ and $z$ be distinct vertices of $G$. We show that if for any nonadjacent distinct vertices $u$ and $v$ in $V(G)–\{x,z\}$, at least one of $yu$ and $zv$ has degree greater than or equal to $d$ in $G$, then for any subset $Y$ of $V(G)–\{x,z\}$ having cardinality at most $k–1$, $G$ contains a path which has $x$ and $z$ as its endvertices, passes through all vertices in $Y$, and has length at least $2d–2$.

For a graph $G$, a partiteness $k\ge 2$ and a number of colours $c$, we define the multipartite Ramsey number $r_k^c(G)$ as the minimum value $m$ such that, given any colouring using $c$ colours of the edges of the complete balanced $k$-partite graph with $m$ vertices in each partite set, there must exist a monochromatic copy of $G$. We show that the question of the existence of $r_k^c(G)$ is tied up with what monochromatic subgraphs are forced in a $c$-colouring of the complete graph $K_k$. We then calculate the values for some small $G$ including $r_3^2(C_4)=3,r_4^2(C_4)=2,r_3^3(C_4)=7$ and $r_3^2(C_6)=3$.

A graph $G$ with vertex set $V(G)$ is an exact $n$-step domination graph if there is some subset $S\subseteq V(G)$ such that each vertex in $G$ is distance $t$ from exactly one vertex in $S$. Given a set $A\subseteq \mathbb{N}$, we characterize cycles $C_t$ with sets $S\subseteq V(C_t)$ that are simultaneously $a$-step dominating for precisely those $a\in A$. Using Polya’s method, we compute the number of $t$-step dominating sets for a cycle $C_t$ that are distinct up to automorphisms of $C_t$. Finally, we generalize the notion of exact $t$-step domination.

Let $D$ be a digraph. The competition-common enemy graph of $D$ has the same set of vertices as $D$ and an edge between vertices $u$ and $v$ if and only if there are vertices $w$ and $x$ in $D$ such that $(w,u),(w,v),(u,x)$, and $(v,x)$ are arcs of $D$. We call a graph a CCE-graph if it is the competition-common enemy graph of some digraph. We also call a graph $G=(V,E)$ CCE-orientable if we can give an orientation $F$ of $G$ so that whenever $(w,u),(w,v),(u,x)$, and $(v,x)$ are in $F$, either $(u,v)$ or $(v,u)$ is in $F$. Bak $etal.[1997]$ found a large class of graphs that are CCE-orientable and proposed an open question of finding graphs that are not CCE-orientable. In this paper, we answer their question by presenting two families of graphs that are not CCE-orientable. We also give a CCE-graph that is not CCE-orientable, which answers another question proposed by Bak $etal.[1997]$. Finally, we find a new family of graphs that are CCE-orientable.