In 1948, de Bruijn and Erdős proved that every finite linear space on \(v\) points and with \(6\) lines fulfils the inequality \(b \geq v\), and the equality holds if the linear space is a (possibly degenerate) projective plane. This result led to the problem of classifying finite linear spaces on \(v\) points and with \(b = v + s\) lines, \(s \geq 1\). This paper contains the classification of finite linear spaces on \(v\) points and with \(b = v + 4\) lines.

For a vertex \(v\) of a connected graph \(G\) and a subset \(S\) of \(V(G)\), the distance between \(v\) and \(S\) is \(d(v,S) = \min\{d(v,z)|z \in S\}\). For an ordered \(k\)-partition \(\Pi = \{S_1,S_2,\ldots,S_k\}\) of \(V(G)\), the code of \(v\) with respect to \(\Pi\) is the \(k\)-vector \(c_\Pi(v) = (d(v, S_1), d(v, S_2), \ldots, d(v,S_k))\). The \(k\)-partition \(\Pi\) is a resolving partition if the \(k\)-vectors \(c_\Pi(v), v \in V(G)\), are distinct. The minimum \(k\) for which there is a resolving \(k\)-partition of \(V(G)\) is the partition dimension \(pd(G)\) of \(G\). A resolving partition \(\Pi = \{S_1,S_2,\ldots,S_k\}\) of \(V(G)\) is a resolving-coloring if each \(S_i\) (\(1 \leq i \leq k\)) is independent and the resolving-chromatic number \(\chi_r(G)\) is the minimum number of colors in a resolving-coloring of \(G\). A resolving partition \(\Pi = \{S_1,S_2,\ldots,S_k\}\) is acyclic if each subgraph \((S_i)\) induced by \(S_i\) (\(1 \leq i \leq k\)) is acyclic in \(G\). The minimum \(k\) for which there is a resolving acyclic \(k\)-partition of \(V(G)\) is the resolving acyclic number \(\alpha_r(G)\) of \(G\). Thus \(2 \leq pd(G) < \alpha_r(G) \leq \chi_r(G) \leq n\) for every connected graph \(G\) of order \(n \geq 2\). We present bounds for the resolving acyclic number of a connected graph in terms of its arboricity, partition dimension, resolving-chromatic number, diameter, girth, and other parameters. Connected graphs of order \(n \geq 3\) having resolving acyclic number \(2, n,\) or \(n-1\) are characterized.

Let \(p\) and \(q\) be distinct primes with \(p > q\) and \(n\) a positive integer. In this paper, we consider the set of possible cross numbers for the cyclic groups \(\mathbb{Z}_{2p^n}\) and \(\mathbb{Z}_{pq}\). We completely determine this set for \(\mathbb{Z}_{2p^n}\) and also \(\mathbb{Z}_{pq}\) for \(q = 3, q = 5\) and the case where \(p\) is sufficiently larger than \(g\). We view the latter result in terms of an upper bound for this set developed in a paper of Geroldinger and Schneider [8] and show precisely when this upper bound is an equality.

It is known that triangles with vertices in the integral lattice \(\mathbb{Z}^2\) and exactly one interior lattice point can have \(3, 4, 6, 8\), and \(9\) lattice points on their boundaries. No such triangles with \(5\), nor \(7\), nor \(n \geq 10\) boundary lattice points exist. The purpose of this note is to study an analogous property for Hex-triangles, that is, triangles with vertices in the set \(H\) of corners of a tiling of \(\mathbb{R}^2\) by regular hexagons of unit edge. We show that any Hex-triangle with exactly one interior \(H\)-point can have \(3, 4, 5, 6, 7, 8,\) or \(10\), \(H\)-points on its boundary and cannot have \(9\) nor \(n \geq 11\) such points.

The problem of classification of Hadamard matrices becomes an NP-hard problem as the order of the Hadamard matrices increases. In this paper, we use a new criterion which inspired us to develop an efficient algorithm to investigate the lower bound of inequivalent Hadamard matrices of order \(36\). Using four \((1,-1)\) circulant matrices of order \(9\) in the Goethals-Seidel array, we obtain many new Hadamard matrices of order \(36\) and we show that there are at least \(1036\) inequivalent Hadamard matrices for this order.

We prove the gracefulness of two classes of graphs.

Let \(G\) be a graph with \(q\) edges. \(G\) is numbered if each vertex \(v\) is assigned a non-negative integer \(\phi(v)\) and each edge \(uv\) is assigned the value \(|\phi(u) – \phi(v)|\). The numbering is called graceful if, further, the vertices are labelled with distinct integers from \(\{0, 1, 2, \ldots, q\}\) and the edges with integers from \(1\) to \(q\). A graph which admits a graceful numbering is said to be graceful. For the literature on graceful graphs see [1, 2] and the relevant references given in them.

Let \(G\) be a graph and let \(c\) be a coloring of its edges. If the sequence of colors along a walk of \(G\) is of the form \(a_1, \ldots, a_n, a_1, \ldots, a_n\), the walk is called a square walk. We say that the coloring \(c\) is square-free if any open walk is not a square and call the minimum number of colors needed so that \(G\) has a square-free coloring a walk Thue number and denote it by \(\pi_w(G)\). This concept is a variation of the Thue number introduced by Alon, Grytczuk, Hatuzczak, and Riordan in [2].

Using the walk Thue number, several results of [1] are extended. The Thue number of some complete graphs is extended to Hamming graphs. This result (for the case of hypercubes) is used to show that if a graph \(G\) on \(n\) vertices and \(m\) edges is the subdivision graph of some graph, then \(\pi_w(G) \leq n – \frac{m}{2}\). Graph products are also considered. An inequality for the Thue number of the Cartesian product of trees is extended to arbitrary graphs and upper bounds for the (walk) Thue number of the direct and the strong products are also given. Using the latter results, the (walk) Thue number of complete multipartite graphs is bounded, which in turn gives a bound for arbitrary graphs in general and for perfect graphs in particular.