It is known that there exists a one-to-one correspondence between the classes of equivalent \([n, n-k, 4]\)-codes over \(\mathrm{GF}(q)\) and the classes of projectively equivalent complete \(n\)-caps in \(\mathrm{PG}(k-1, q)\) (see [{20}], [{40}]). Hence all results on caps can be translated in terms of such codes. This fact stimulated many researches on the fundamental problem of determining the spectrum of the values of \(k\) for which there exist complete \(k\)-caps in \(\mathrm{PG}(n, q)\). This paper reports the result of a computer search for the spectrum of \(k\)’s that occur as a size of a complete \(k\)-cap in some finite projective spaces. The full catalog of such sizes \(k\) is given in the following projective spaces: \(\mathrm{PG}(3, q)\), for \(q \leq 5\), \(\mathrm{PG}(4, 2)\), \(\mathrm{PG}(4, 3)\), \(\mathrm{PG}(5, 2)\). Concrete examples of such caps are presented for each possible \(k\).\(^*\)

It is known (cf. {Hamada} [12] and {BrouwerEupen} and van Eupen [2] ) that (1) there is no ternary \([230, 6, 153]\) code meeting the Griesmer bound but (2) there exists a ternary \([232, 6, 153]\) code. This implies that \(n_3(6, 153) = 231\) or \(232\), where \(n_3(k, d)\) denotes the smallest value of \(n\) for which there exists a ternary \([n, k, d]\) code. The purpose of this paper is to prove that \(n_3(6, 153) = 232\) by proving the nonexistence of ternary \([231, 6, 153]\) codes.

If \(D\) is an acyclic digraph, its competition graph is an undirected graph with the same vertex set and an edge between vertices \(x\) and \(y\) if there is a vertex \(a\) so that \((x,a)\) and \((y,a)\) are both arcs of \(D\). If \(G\) is any graph, \(G\) together with sufficiently many isolated vertices is a competition graph, and the competition number of \(G\) is the smallest number of such isolated vertices. Roberts \([1978]\) gives an elimination procedure for estimating the competition number and Opsut \([1982]\) showed that this procedure could overestimate. In this paper, we modify that elimination procedure and then show that for a large class of graphs it calculates the competition number exactly.

A new concept of genus for finite groups, called stiff genus, is developed. Cases of stiff embeddings in orientable or nonorientable surfaces are dealt with. Computations of stiff genus of several classes of abelian and non-abelian groups are presented. A comparative analysis between the stiff genus and the Tucker symmetric genus is also undertaken.

For each admissible \(v\) we exhibit a \(\mathrm{H}(v, 3, 1)\) with a spanning set of minimum cardinality and a \(\mathrm{H}(v, 3, 1)\) with a scattering set of maximum cardinality.

Using the Jacobi triple product identity and the quintuple product identity, we obtain identities involving several partition functions.

A snark is a simple, cyclically \(4\)-edge connected, cubic graph with girth at least \(5\) and chromatic index \(4\). We give a complete list of all snarks of order less than \(30\). Motivated by the long standing discussion on trivial snarks (i.e. snarks which are reducible), we also give a brief survey on different reduction methods for snarks. For all these reductions we give the complete numbers of irreducible snarks of order less than \(30\) and the number of nonisomorphic \(3\)-critical subgraphs of these graphs. The results are obtained with the aid of a computer.

We give short proofs of theorems of Nash-Williams (on edge-partitioning a graph into acyclic subgraphs) and of Tutte (on edge-partitioning a graph into connected subgraphs). We also show that each theorem can be easily derived from the other.

We derive several new lower bounds on the size of ternary covering codes of lengths \(6\), \(7\) and \(8\) and with covering radii \(2\) or \(3\).

We show that every complete graph \(K_n\), with an edge-colouring without monochromatic triangles, has a properly coloured Hamiltonian path.

In this paper we prove some basic properties of the \(g\)-centroid of a graph defined through \(g\)-convexity. We also prove that finding the \(g\)-centroid of a graph is NP-hard by reducing the problem of finding the maximum clique size of \(G\) to the \(g\)-centroidal problem. We give an \(O(n^2)\) algorithm for finding the \(g\)-centroid for maximal outer planar graphs, an \(O(m + n\log n)\) time algorithm for split graphs and an \(O(m^2)\) algorithm for ptolemaic graphs. For split graphs and ptolemaic graphs we show that the \(g\)-centroid is in fact a complete subgraph.

In this paper, we show that if \(G\) is a connected \(SN2\)-locally connected claw-free graph with \(\delta(G) \geq 3\), which does not contain an induced subgraph \(H\) isomorphic to either \(G_1\) or \(G_2\) such that \(N_1(x,G)\) of every vertex \(x\) of degree \(4\) in \(H\) is disconnected, then every \(N_2\)-locally connected vertex of \(G\) is contained in a cycle of all possible lengths and so \(G\) is pancyclic. Moreover, \(G\) is vertex pancyclic if \(G\) is \(N_2\)-locally connected.

A matching in a graph \(G\) is a set of independent edges and a maximal matching is a matching that is not properly contained in any other matching in \(G\). A maximum matching is a matching of maximum cardinality. The number of edges in a maximum matching is denoted by \(\beta_1(G)\); while the number of edges in a maximal matching of minimum cardinality is denoted by \(\beta^-_1(G)\). Several results concerning these parameters are established including a Nordhaus-Gaddum result for \(\beta^-_1(G)\). Finally, in order to compare the maximum matchings in a graph \(G\), a metric on the set of maximum matchings of \(G\) is defined and studied. Using this metric, we define a new graph \(M(G)\), called the matching graph of \(G\). Several graphs are shown to be matching graphs; however, it is shown that not all graphs are matching graphs.

In this paper we consider interval colourings — edge colourings of bipartite graphs in which the colours represented at each vertex form an interval of integers. These colourings, corresponding to certain types of timetables, are not always possible. In the present paper it is shown that if a bipartite graph with bipartition \((X,Y)\) has all vertices of \(X\) of the same degree \(d_X = 2\) and all vertices of \(Y\) of the same degree \(d_y\), then an interval colouring can always be established.

Let \(v\) and \(u\) be positive integers. It is shown in this paper that the necessary condition for the existence of a directed \(\mathrm{TD}(5,v)\)-\(\mathrm{TD}(5,u)\), namely \(v \geq 4u\), is also sufficient.

Initiated by a recent question of Erdhos, we give lower bounds on the size of a largest \(k\)-partite subgraph of a graph. Also, the corresponding problem for uniform hypergraphs is considered.

Let \(G = (V, E)\) be a graph and \(k \in \mathbb{Z}^+\) such that \(1 \leq k \leq |V|\). A \(k\)-subdominating function (KSF) to \(\{-1, 0, 1\}\) is a function \(f: V \to \{-1, 0, 1\}\) such that the closed neighborhood sum \(f(N[v]) \geq 1\) for at least \(k\) vertices of \(G\). The weight of a KSF \(f\) is \(f(V) = \sum_{v \in V} f(v)\). The \(k\)-subdomination number to \(\{-1, 0, 1\}\) of a graph \(G\), denoted by \(\gamma^{-101}_{k_s}(G)\), equals the minimum weight of a KSF of \(G\). In this paper, we characterize minimal KSF’s, calculate \(\gamma^{-101}_{k_s}(G)\) for an arbitrary path \(P_n\), and determine the least order of a connected graph \(G\) for which \(\gamma^{-101}_{k_s}(G)=-m\) for an arbitrary positive integer \(m\).

Let \(G\) be a simple graph of order \(n\) having a maximum matching \(M\). The deficiency \( def(G)\) of \(G\) is the number of vertices unsaturated by \(M\). In this paper, we find lower bounds for \(n\) when \( def(G)\) and the minimum degree (or maximum degree) of vertices are given. Further, for every \(n\) not less than the bound and of the same parity as \( def(G)\), there exists a graph \(G\) with the given deficiency and minimum (maximum) degree.

In this paper, we count the number of isomorphism classes of bipartite \(n\)-cyclic permutation graphs up to positive natural isomorphism and show that it is equal to the number of double cosets of the dihedral group \(D_n\) in the subgroup \(B_n\) of the symmetric group \(S_n\), consisting of parity-preserving or parity-reversing permutations.

Let \(\alpha(G)\) denote the independence number of a graph \(G\) and let \(G \times H\) be the direct product of graphs \(G\) and \(H\). Set \(\underline{\alpha}(G\times H) = \max\{\alpha(G) – |H|, \alpha(H) – |G|\}\). If \(G\) is a path or a cycle and \(H\) is a path or a cycle, then \(\alpha(G \times H) = \underline{\alpha}(G \times H)\). Moreover, this equality holds also in the case when \(G\) is a bipartite graph with a perfect matching and \(H\) is a traceable graph. However, for any graph \(G\) with at least one edge and for any \(i \in \mathbb{N}\), there is a graph \(H_c\) such that \(\alpha(G \times H ) > \underline{\alpha}(G \times H ) + i\).

Our main aim is to show that the Randi\’e weight of a connected graph of order \(n\) is at least \(\sqrt{n – 1}\). As shown by the stars, this bound is best possible.

New class \(\mathcal{GBG}_{\overrightarrow{k}}\), of generalized de Bruijn multigraphs of rank \({\overrightarrow{k}}\in{N}^m\), is introduced and briefly characterized. It is shown, among the others, that every multigraph of \(\mathcal{GBG}_{\overrightarrow{k}}\) is connected, Eulerian and Hamiltonian. Moreover, it consists of the subgraphs which are isomorphic with the de Bruijn graphs of rank \(r=\sum_{i=1}^{m} (d_1,\dots,d_m)\in\{0.1\}^m\). Then, the subgraphs of every multigraph of \(\mathcal{GBG}_{\overrightarrow{k}}\), called the \({\overrightarrow{k}}\)-factors, are distinguished.

An algorithm, with small time and space complexities, for the construction of the \({\overrightarrow{k}}\)-factors, in particular the Hamiltonian circuits, is given. At the very end, a few open problems are put forward.

A graph \(G\) is collapsible if for every even subset \(R \subseteq V(G)\), there is a spanning connected subgraph of \(G\) whose set of odd degree vertices is \(R\). A graph is supereulerian if it contains a spanning closed trail. It is known that every collapsible graph is supereulerian. A graph \(G\) of order \(n\) is said to satisfy a Fan-type condition if \(\max\{d(u),d(v)\} \geq \frac{n}{(g-2)p} – \epsilon\) for each pair of vertices \(u,v\) at distance two, where \(g \in \{3,4\}\) is the girth of \(G\), and \(p \geq 2\) and \(\epsilon \geq 0\) are fixed numbers. In this paper, we study the Fan-type conditions for collapsible graphs and supereulerian graphs.

Let \(n \geq 1\) be an integer. The closed \(n\)-neighborhood \(N_n[u]\) of a vertex \(u\) in a graph \(G = (V, E)\) is the set of vertices \(\{v | d(u,v) \leq n\}\). The closed \(n\)-neighborhood of a set \(X\) of vertices, denoted by \(N_n[X]\), is the union of the closed \(n\)-neighborhoods \(N_n[v]\) of vertices \(u \in X\). For \(X \subseteq V(G)\), if \(N_n[x] – N_n[X – \{u\}] = \emptyset\), then \(u\) is said to be \(n\)-redundant in \(X\). A set \(X\) containing no \(n\)-redundant vertex is called \(n\)-irredundant. The \(n\)-irredundance number of \(G\), denoted by \(ir_n(G)\), is the minimum cardinality taken over all maximal \(n\)-irredundant sets of vertices of \(G\). The upper \(n\)-irredundance number of \(G\), denoted by \(IR_n(G)\), is the maximum cardinality taken over all maximal \(n\)-irredundant sets of vertices of \(G\). In this paper we show that the decision problem corresponding to the computation of \(ir_n(G)\) for bipartite graphs \(G\) is NP-complete. We then prove that this also holds for augmented split graphs. These results extend those of Hedetniemi, Laskar, and Pfaff (see [7]) and Laskar and Pfaff (see [8]) for the case \(n = 1\). Lastly, applying the general method described by Bern, Lawler, and Wong (see [1]), we present linear algorithms to compute the \(2\)-irredundance and upper \(2\)-irredundance numbers for trees.

Some properties of finite projective planes are used to obtain some new pairwise balanced designs with consecutive block sizes, by deleting configurations spanned by lines.

We give a short survey of the best known lower bounds on \(K(n, 1)\), the minimum cardinality of a binary code of length \(n\) and covering radius \(1\). Then we prove new lower bounds on \(K(n, 1)\), e.g.
\[K(n,1)\geq \frac{(5n^2-13n+66)2^n}{(5n^2-13n+46)(n+1)}\] when \(n \equiv 5 \pmod{6}\)
which lead to several numerical improvements.

In this paper, we study path-factors and path coverings of a claw-free graph and those of its closure. For a claw-free graph \(G\) and its closure \( cl(G)\), we prove:(1) \(G\) has a path-factor with \(r\) components if and only if \( cl(G)\) has a path-factor with \(r\) components,(2) \(V(G)\) is covered by \(k\) paths in \(G\) if and only if \(V( cl(G))\) is covered by \(k\) paths in \( cl(G)\).

Let \(G = (V,E)\) be a connected graph. Let \(\gamma_c(G), d_c(G)\) denote the connected domination number, connected domatic number of \(G\), respectively. We prove that \(\gamma_c(G) \leq 3d_c(G^c)\) if the complement of \(G\) is also connected. This confirms a conjecture of Hedetniemi and Laskar (1984), and Sun (1992). Examples are given to show that equality may occur.

A method of construction of quasi-multiple balanced incomplete block \((BIB)\) designs from certain group divisible designs is described. This leads to a series of quasi-multiple designs of symmetric BIB designs and new non-isomorphic solutions of designs listed as unknown in the tables of Mathon and Rosa \([{3,4}]\). In the process a series of semi-regular group divisible designs is also obtained.