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.

Denote the total domination number of a graph \(G\) by \(\gamma_t(G)\). A graph \(G\) is said to be total domination edge critical, or simply \(\gamma_t\)-critical, if \(\gamma_t(G+e) < \gamma_t(G)\) for each edge \(e \in E(\overline{G})\). For \(\gamma_t\)-critical graphs \(G\), that is, \(\gamma_t\)-critical graphs with \(\gamma_t(G) = 3\), the diameter of \(G\) is either \(2\) or \(3\). We study the \(3_t\)-critical graphs \(G\) with \(diam(G) = 2\).

We consider two possible methods of embedding a (simple undirected) graph into a uniquely vertex colourable graph. The first method considered is to build a \(K\)-chromatic uniquely vertex colourable graph from a \(k\)-chromatic graph \(G\) on \(G\cup K_k\), by adding a set of new edges between the two components. This gives rise to a new parameter called fixing number (Daneshgar (1997)). Our main result in this direction is to prove that a graph is uniquely vertex colourable if and only if its fixing number is equal to zero (which is a counterpart to the same kind of result for defining numbers proved by Hajiabolhassan et al. (1996)).

In our second approach, we try a more subtle method of embedding which gives rise to the parameters \(t_r\)-fixer and \(\tau_r\)-index (\(r = 0, 1\)) for graphs. In this approach we show the existence of certain classes of \(u\)-cores, for which, the existence of an extremal graph provides a counter example for Xu’s conjecture.

Necessary and sufficient conditions are given for a Steiner triple system of order \(t\) admitting an automorphism consisting of one large cycle, cycles of length \(8\), and a fixed point, with \(t \leq 4\). Necessary conditions are given for all \(t \geq 1\).

In this note we prove that the bipartite Ramsey number for \(K_{2,n}\) with \(q\) colors does not exceed \((n-1)q^2+q+1-\left\lceil\sqrt{q}\right\rceil\), improving the previous upper bound by \(\left\lceil\sqrt{q}\right\rceil-2\).