In \(1990\), Anderson et al. \([1]\) generalized the competition graph of a digraph to the competition multigraph of a digraph and defined the multicompetition number of a multigraph. The competition multigraph \(CM(D)\) of a digraph \(D = (V, A)\) is the multigraph \(M = (V, E’)\) where two vertices of \(V\) are joined by \(k\) parallel edges if and only if they have exactly \(\ell\) common preys in \(D\). The multicompetition number \(k^*(M)\) of the multigraph \(M\) is the minimum number \(p\) such that \(M \cup I_p\) is the competition multigraph of an acyclic digraph, where \(I_k\) is a set of \(p\) isolated vertices. In this paper, we study the multicompetition numbers for some multigraphs and generalize some results provided by Kim and Roberts \([9]\), and by Zhao and He \([18]\) on general competition graphs, respectively.

Frank Harary contributed numerous questions to a variety of topics in graph theory. One of his favourite topics was the Reconstruction Problem, which, in its first issue in \(1977\), the Journal of Graph Theory described as the major unsolved problem in the field. Together with Plantholt, Frank Harary initiated the study of reconstruction numbers of graphs. We shall here present a survey of some of the work done on reconstruction numbers, focusing mainly on the questions which this work leaves open.

An upper bound of the basis number of the lexicographic product of two graphs from the basis number of the factors is presented. Furthermore, the basis numbers of the lexicographic product of some classes of graphs is determined.

In this paper, we prove that for any graph \(G\), \(\lambda(G^{+++}) = \delta(G^{-++})\) and all but for a few exceptions, \(G^{-++}\) is super edge-connectivity where \(G^{-++}\) is the transformation graph of a graph \(G\) introduced in \([1]\).

A graph-pair of order \(t\) is two non-isomorphic graphs \(G\) and \(H\) on \(t\) non-isolated vertices for which \(G \cup H \cong K_t\) for some integer \(t \geq 4\). Given a graph-pair \((G,H)\), we say \((G, H)\) divides some graph \(K\) if the edges of \(K\) can be partitioned into copies of \(G\) and \(H\) with at least one copy of \(G\) and at least one copy of \(H\). We will refer to this partition as a \((G, H)\)-\(multidecomposition\) of \(K\).

In this paper, we consider the existence of multidecompositions of \(K_n – F\) into graph-pairs of order \(5\) where \(F\) is a Hamiltonian cycle or (almost) \(1\)-factor.

The upper chromatic number \(\overline{\chi}_u(\mathcal{H})\) of a \(C\)-hypergraph \(\mathcal{H} = (X, C)\) is the maximum number of colors that can be assigned to the vertices of \(\mathcal{H}\) in such a way that each \(C \in \mathcal{C}\) contains at least a monochromatic pair of vertices. This paper gives an upper bound for the upper chromatic number of Steiner triple systems of order \(n\) and proves that it is best possible for any \(n (\equiv 1 \text{ or } 3 \pmod{6})\).

A map is called Unicursal if it has exactly two vertices of odd valency. A near-triangulation is a map with all but one of its faces triangles. We use the enufunction approach to enumerate rooted Unicursal planar near-triangulations with the valency of the root-face and the number of non-rooted faces as parameters.

An edge coloring is proper if no two adjacent edges are assigned the same color and vertex-distinguishing proper coloring if it is proper and incident edge sets of every two distinct vertices are assigned different sets of colors. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph \(G\) is denoted by \(\overline{\chi}'(G)\). In this paper, we prove that \(\overline{\chi}'(G) \leq \Delta(G) + {4}\) if \(G = (V, E)\) is a connected graph of order \(n \geq 3\) and \(\sigma_2(G) \geq n\), where \(\sigma_2(G) = \min\{d(x) + d(y) | xy \in E(G)\}\).

In this paper, we study the minimum distance between the set of bent functions and the set of \(1\)-resilient Boolean functions and present lower bounds on that. The first bound is proved to be tight for functions up to \(10\) input variables and a revised bound is proved to be tight for functions up to \(14\) variables. As a consequence, we present a strategy to modify the bent functions, by toggling some of its outputs, in getting a large class of \(1\)-resilient functions with very good nonlinearity and autocorrelation. In particular, the technique is applied up to \(14\)-variable functions and we show that the construction provides a large class of \(1\)-resilient functions reaching currently best known nonlinearity and achieving very low autocorrelation values which were not known earlier. The technique is sound enough to theoretically solve some of the mysteries of \(8\)-variable, \(1\)-resilient functions with maximum possible nonlinearity. However, the situation becomes complicated from \(10\) variables and above, where we need to go for complicated combinatorial analysis with trial and error using computational facility.

In this paper, we characterize the variety of quasi-groups isotopic to abelian groups by four-variable identities.