The distance of a vertex \(u\) in a connected graph \(G\) is defined by \(\sigma_G(u) := \sum_{v \in V(G)} d(u, v)\), and the distance of \(G\) is given by \(\sigma(G) = \frac{1}{2} \sum_{u \in V(G)} \sigma(u) (= \sum_{\{u,v\} \subseteq V(G)} d(u, v)\). Thus, the average distance between vertices in a connected graph \(G\) of order \(n\) is \(\frac{\sigma(G)}{\binom{n}{2}}\). These graph invariants have been studied for the past fifty years. Here, we discuss some known properties and present a few new results, together with several open problems. We focus on trees.

Let \(\chi^*(G)\) denote the minimum number of colors required in a coloring \(c\) of the vertices of \(G\) where for adjacent vertices \(u, v\) we have \(c(N_G[u]) \neq c(N_G[v])\) when \(N_G[u] \neq N_G[v]\) and \(c(u) \neq c(v)\) when \(N_G[u] = N_G[v]\). We show that the problem of deciding whether \(\chi^*(G) \leq n\), where \(n \geq 3\), is NP-complete for arbitrary graphs. We find \(\chi^*(G)\) for several classes of graphs, including bipartite graphs, complete multipartite graphs, as well as cycles and their complements. A sharp lower bound is given for \(\chi^*(G)\) in terms of \(\chi(G)\) and an upper bound is given for \(\chi^*(G)\) in terms of \(\Delta(G)\). For regular graphs with girth at least four, we give substantially better upper bounds for \(\chi^*(G)\) using random colorings of the vertices.

A weak repetition in a string consists of two or more adjacent substrings which are permutations of each other. We describe a straightforward \(\Theta(n^2)\) algorithm which computes all the weak repetitions in a given string of length \(n\) defined
on an arbitrary alphabet \(A\). Using results on Fibonacci and other simple strings, we prove that this algorithm is asymptotically optimal over all known encodings of the output.

An algorithm is presented which, when given the non-isomorphic designs with given parameters, generates all the trades in each of the designs. The lists of trades generated by the algorithm were used to find the sizes, previously unknown, of smallest defining sets of the \(21\) non-isomorphic \(2\)-(10, 5, 4) designs. Consideration of trades in a design to isomorphic and to non-isomorphic designs led to two variations on the concept of defining sets. The lists of trades were then used to find the sizes of these smallest member and class defining sets, for five parameter sets.

The present paper studies bisectable trees, i.e., trees whose edges can be colored by two colors so that the induced monochromatic subgraphs are isomorphic. It is proved that the number of edges that have to be removed from a tree with maximum degree three to make it bisectable can be bounded by an absolute constant.

We study the maximal intersection number of known Steiner systems and designs obtained from codes. By using a theorem of Driessen, together with some new observations, we obtain many new designs.

Taking as blocks some subspace pairs in a finite unitary geometry, we construct a number of new Balanced Incomplete Block (BIB) designs and Partially Balanced Incomplete Block (PBIB) designs, and also give their parameters.

The support size of a factorization is the sum over the factors of the number of distinct edges in each factor. The spectrum of support sizes of \(l\lambda\)-factorizations of \(\lambda K_n\) and \(\lambda K_{n,n}\) are completely determined for all \(\lambda\) and \(n\).

Latin interchanges have been used to establish the existence of critical sets in Latin squares, to search for subsquare-free Latin squares, and to investigate the intersection sizes of Latin squares. Donald Keedwell was the first to study Latin interchanges in their own right. This paper builds on Keedwell’s work and proves new results about the existence of Latin interchanges.