1 Introduction

An outstanding class of problems in network design has to do with the construction of large networks subject to certain restrictions. Some common restrictions are, for instance, an upper bound on the number of connections attached to each node (the degree of the node), or an upper bound on the number of hops that a message has to travel from an arbitrary source node to an arbitrary target node (the diameter of the network).

Let us first consider networks with bi-directional links (i.e. undirected graphs). If we denote the maximum degree of any node by \(\Delta \) and the diameter of the network by D, then it is well known that the maximum number of nodes \(N_{\Delta ,D}\) is bounded above by

$$\begin{aligned} \begin{aligned} N_{\Delta ,D} \le M_{\Delta ,D}&= 1 + \Delta + \Delta (\Delta -1) + \cdots + \Delta (\Delta -1)^{D-1} \\&= \left\{ \begin{array}{ll} 1 + \Delta \ \frac{(\Delta -1)^{D} - 1}{\Delta -2} &{} \hbox { if}\ \Delta > 2 \\ 2D+1 &{} \hbox { if}\ \Delta = 2 \\ \end{array}\right. \end{aligned} \end{aligned}$$
(1)

The upper bound \(M_{\Delta ,D}\) is known as the Moore bound, and a network with \(M_{\Delta ,D}\) nodes is called a Moore graph. The Moore bound is only attainable for a few combinations of \(\Delta \) and D [19]. Nevertheless, for those combinations of \(\Delta \) and D where the Moore bound is not attainable, we can still strive to construct networks with as many nodes as possible. This optimization problem is known in the graph-theoretic literature as the Degree/Diameter Problem, or DDP, for short.

DDP can be formulated both for undirected graphs (as above) as well as for digraphs. In the latter case we will denote by \(\overrightarrow{N}_{d,k}\) the maximum number of nodes that can be attained by a digraph of maximum outdegree d and diameter k, and the corresponding upper bound would be:

$$\begin{aligned} \overrightarrow{N}_{d,k} \le \overrightarrow{M}_{d,k} = 1 + d + d^2 + \dots + d^k = \left\{ \begin{array}{ll} \frac{d^{k+1}-1}{d-1} &{} \hbox { if}\ d > 1 \\ k+1 &{} \hbox { if}\ d = 1 \\ \end{array}\right. \end{aligned}$$
(2)

A lot of research has been done on particular versions of the problem, namely when the graphs or digraphs are restricted to a certain class, such as the class of Cayley graphs [2, 11, 16, 32], Cayley graphs of abelian groups [6], or circulant graphs [17, 22, 33]. In this paper we are revisiting the problem for the class of circulant graphs and digraphs.

Circulant graphs and digraphs possess other interesting properties from the point of view of their potential applications. For example, they are easy to construct, and are vertex transitive, which means that all nodes are essentially identical. That is a great advantage from the point of view of algorithm design, and that is one of the reasons why circulant graphs and digraphs have been used as topologies for interconnection networks and parallel computers. On the negative side, the upper bound on the number of vertices for the class of circulant graphs is substantially smaller than the general Moore bound.

Besides striving to construct large circulant networks with bounded degree and diameter, we also pay attention to the design of efficient routing algorithms. Greedy routing is a simple strategy that can be used in circulant networks, and other related network topologies [9]. Basically, the greedy routing strategy consists of always forwarding the message packet to the neighbour node that minimizes the distance to the target node. Needless to say, in an arbitrary network this strategy does not always result in the shortest route to the target node. However, in some networks it does. Our aim is to construct large circulant networks for which the greedy routing algorithm always outputs the shortest route.

The paper is organized as follows: in Sect. 2, we set the notation and state some definitions and results that will be needed throughout the rest of the paper. In Sect. 3, we establish the connection between greedy routing in circulant graphs and the change-making problem, a combinatorial problem in numerical semigroups. In Sect. 4, we investigate some families of large circulant networks that have been proposed in the literature, and ascertain whether they satisfy the property that greedy routing always produces the shortest route. Section 5 is devoted to studying some number sequences whose prefixes have the greedy property mentioned above. Then, Sect. 6 provides some large circulant graphs (both directed and undirected), which have the greedy routing property. The paper ends with some open problems and future research directions.

2 Definitions and Basic Facts

In this section, we define some notation and concepts that are needed throughout the paper, mainly dealing with circulant graphs. We have mostly followed the notation and style of [8], which contains some additional details. References [12, 20] are also relevant sources in directed and undirected circulants, respectively.

A directed circulant graph C(n; S) is a Cayley graph on the cyclic group \(\mathbb {Z}_n\), with connection set \(S = \{ s_1, \ldots , s_t \}\), such that S does not include any pair consisting of a generator \(s_i\) and its inverse. In other words, every vertex i is connected by an arc to the vertices \(i+s_1, i+s_2, \ldots , i+s_t\), where addition is performed modulo n. So, the out-degree of every vertex is \(\vert S \vert \). In order to simplify the notation, we drop the curly brackets \(\{ \}\) in the specification of the set S in C(n; S) and write \(C(n; s_1, \ldots , s_t)\). It is well known that C(n; S) is strongly connected if, and only if, \(\gcd (n, s_1, \ldots , s_t) = 1\).

In turn, an undirected circulant graph C(n; S) is a Cayley graph on the cyclic group \(\mathbb {Z}_n\), with a symmetric connection set S (i.e. \(S = S^{-1}\), or \(S = -S\) in additive notation).

C(n; S) is vertex-transitive, since it is a Cayley graph. The degree of C(n; S) is \(\Delta = \vert S \vert \), and its order is obviously n. A circulant graph can also be defined as a graph of n vertices whose adjacency matrix is circulant [7].

Regarding the degree, we distinguish two cases:

  1. 1.

    Even degree: \(\Delta = 2t\). In that case, \(S = \{ \pm s_1, \ldots , \pm s_t \}\), where \(1 \le s_1< \cdots< s_t < \frac{n}{2}\).

  2. 2.

    Odd degree: \(\Delta = 2t+1\). In that case, \(S = \{ \pm s_1, \ldots , \pm s_t, \frac{n}{2} \}\), where \(1 \le s_1< \cdots< s_t < \frac{n}{2}\). It follows that odd degree is only possible when n is even.

As in the directed case, an undirected circulant C(n; S) is connected if, and only if, \(\gcd (n, s_1, \ldots , s_t) = 1\). If \(\gcd (n, r) = 1\), then C(n; S) is isomorphic to C(n; rS), where multiplication is taken modulo n. In that case we say that the connection sets S and rS are multiplicatively related. It should be noted, however, that two circulant graphs may be isomorphic without their connection sets being multiplicatively related [7, 23].

Now, let \(\overrightarrow{N}^{AC}_{d,k}\) be the number of vertices of the largest abelian Cayley digraph with out-degree d and diameter k; then

$$\begin{aligned} \overrightarrow{N}^{AC}_{d,k} \le {k+d \atopwithdelims ()d} = {k+d \atopwithdelims ()k} \end{aligned}$$
(3)

Since circulant digraphs are a special case of abelian Cayley digraphs, \(\overrightarrow{N}^{AC}_{d,k}\) is also an upper bound for circulant digraphs. Actually, \(\overrightarrow{N}^{AC}_{d,k}\) is the best general upper bound for circulant digraphs known so far (see [6, 15]).

The upper bound in the undirected case is a bit more involved. Let \(N^{AC}_{\Delta ,D}\) be the number of vertices of the largest abelian Cayley graph with degree \(\Delta \) and diameter D. If \(\Delta = 2t\), then

$$\begin{aligned} N^{AC}_{\Delta ,D} \le F(t,D) = \sum _{i=0}^{t} 2^i {t \atopwithdelims ()i} {D \atopwithdelims ()i} \end{aligned}$$
(4)

This upper bound was proved in [3] and later rediscovered by Muga [22]. As in the undirected case, \(N^{AC}_{\Delta ,D}\) is also the best general upper bound for a circulant graph with degree \(\Delta \) and diameter D known so far [6, 15]. As of today, no smaller general upper bound (yet) exists for circulant graphs, which is quite surprising if we consider that they are a special case of abelian Cayley graphs.

The numbers F(t, D) of Eq. (4) are known as Delannoy numbers (sequence A008288 of [24]), and they arise in several combinatorial and geometric problems [27]. Geometrically, they correspond to the volume of the ball of radius D/2 in the \(L^1\) metric in t dimensions [6, 18, 31].

There is actually a formula that generalizes the aforementioned upper bounds for the directed and the undirected case, in the sense that it allows both directed arcs and undirected edges (see [15]).

Circulant graphs and digraphs are also called multi-loop networks. In particular, circulants with \(t = 2\) and \(t = 3\) generators are called double-loop and triple-loop networks, respectively.

An important special case of multi-loop networks is the case when \(s_1 = 1\), also called chordal rings by some authors. This case will be considered in detail here because it provides a direct link with the change-making problem [26], as we will see next.

3 Making Change and Greedy Routing in Circulant Graphs

Broadly speaking, network routing is the process by which a path is chosen in order to transmit a message across a network. The path is chosen according to different criteria, e.g. the distance to be travelled by the message, fault-tolerance of the communication protocol, network congestion, etc. If the network topology is fixed, then a static routing algorithm can be implemented.

There is an extensive body of work on routing algorithms for specific network topologies, such as circulant networks (see, for instance [10, 21, 30]). However, less attention has been paid to the design of large circulant networks with efficient communication features.

A simple and popular routing strategy is greedy routing, which consists of always forwarding the message packet to the neighbour node that minimizes the distance to the target node, for some distance function defined on the nodes of the network. This strategy makes sense, for instance, in geographically embedded networks, and also in circulant networks [9]. Nevertheless, in an arbitrary network this strategy does not always result in the shortest route to the target node, but in some networks it does. In this section, we will investigate the conditions under which greedy routing results in the best route. As we will see, this problem has already been investigated in a different setting, under the name of change-making problem [25, 26], and it is related to other problems in numerical semigroups.

Let us first note that, since circulant graphs and digraphs are vertex-transitive, the problem of finding a route (optimal or not) from vertex i to vertex j, can be reduced to the problem of finding a route from vertex 0 to vertex k, where k is either \(i-j\) or \(j-i\). Therefore, from now on we may focus on the analysis of routing strategies starting at vertex 0. This establishes a direct connection between the routing problem and the money-changing problem, which we will now recall.

In the money-changing problem we have a set of coin denominations \(S = \{ s_1, \ldots , s_t \}\), with \(1 \le s_1< \cdots < s_t\). Usually we impose the stronger condition that \(s_1 = 1\), so as to be able to make any arbitrary payment, although we will see that this requirement can be relaxed in our setting. We also have a target amount k, and the goal is to make k using as few coins as possible. Mathematically, we are looking for a payment vector \((a_1, \ldots , a_t)\), such that

$$\begin{aligned}&a_i \ge 0, \text{ for } \text{ all } i = 1, \ldots , t \end{aligned}$$
(5)
$$\begin{aligned}&\sum _{i=1}^{t} a_i s_i = k, \end{aligned}$$
(6)
$$\begin{aligned}&\sum _{i=1}^{t} a_i \text{ is } \text{ minimal. } \end{aligned}$$
(7)

The greedy algorithm for making change proceeds as follows

figure a

The payment vector produced by Algorithm 1 is not necessarily optimal (i.e. \({\textsc {GreedyCost}}_S(k) = \sum _{i=1}^{t} a_i\) is not always minimal among all possible payment vectors) but for some sets of denominations we can guarantee that it is optimal.

Let’s take for example two sets of denominations: \(S_1 = \{ 1, 2, 5 \}\) and \(S_2 = \{ 1, 4, 6 \}\), and suppose that we want to represent the quantity 8. With the set \(S_1\), Algorithm 1 produces the representation \(8=5+2+1\), which uses three coins, one of each denomination. In other words, the payment vector would be (1, 1, 1). This payment vector happens to be optimal, i.e. it is impossible to find a representation of 8 using fewer coins of \(S_1\). In fact, it can be proved that with the set \(S_1\), Algorithm 1 produces an optimal representation for any quantity k.

On the other hand, with the set \(S_2\), Algorithm 1 produces the representation \(8=6+1+1\), which again uses three coins, one of denomination 6 and two of denomination 1. However, in this case the payment vector produced by the greedy method is not optimal, since there is a better representation of the quantity 8, namely \(8=4+4\), which uses only two coins.

If a set S of denominations always produces an optimal payment vector for any amount k, then S is called orderly, canonical, or greedy. There is a polynomial-time algorithm that determines whether a given set of denominations is greedy [25, 26], as well as plenty of necessary or sufficient conditions for special families of denomination sets [1, 4].

The most powerful necessary and sufficient condition is given by the so-called one-point theorem (see Theorem 2.1 [1]). Here we state it in a modified form:

Theorem 1

Suppose that \(S = \{ 1, s_2, \ldots , s_t \}\) is a greedy set of denominations, and \(s_{t+1} > s_t\). Now let \(\displaystyle m = \left\lceil \frac{s_{t+1}}{s_t} \right\rceil \). Then \(\hat{S} = \{ 1, s_2, \ldots , s_t, s_{t+1} \}\) is greedy if, and only if, \({\textsc {GreedyCost}}_S(ms_t - s_{t+1}) < m\). \(\square \)

Notice that

$$\begin{aligned} (m-1)s_t +1 \le s_{t+1} \le ms_t, \end{aligned}$$

by the definition of m. A straightforward consequence of the one-point theorem is the following

Corollary 1

(Lemma 7.4 of [1]) Suppose that \(S = \{ 1, s_2, \ldots , s_t \}\) is a greedy set, and \(s_{t+1} = us_t\), for some \(u \in \mathbb {N}\). Then \(\hat{S} = \{ 1, s_2, \ldots , s_t, s_{t+1} \}\) is also greedy. \(\square \)

All the above concepts and results can be extended directly to the routing problem in circulant graphs and digraphs:

Let \(\overrightarrow{\Gamma }\) be a circulant digraph \(C(n; 1, s_2, \ldots , s_t)\), where \(S=\{ 1, s_2, \ldots , s_t \}\) is a greedy system of denominations in the aforementioned sense, and let \(k \in \{ 0, \ldots , n-1 \}\) be an arbitrary vertex of \(\overrightarrow{\Gamma }\). Then, the greedy payment vector \((a_1, a_2, \ldots , a_t)\) gives us the best route from vertex 0 to vertex k, by following the \(s_t\)-arcs \(a_t\) times, the \(s_{t-1}\)-arcs \(a_{t-1}\) times, and so on. A circulant digraph \(C(n; 1, s_2, \ldots , s_t)\) equipped with a greedy connection set will be called greedy, and the payment vector will be the routing vector.

Notice that, if we know the routing vector in advance, we can follow the arcs in any order. For instance, we can start with the \(a_1\) unit steps, then we can follow the \(a_2\) arcs of type \(s_2\), and so on, in increasing order of the sub-index i. That gives us several different optimal routes from vertex 0 to vertex k. More precisely, the number of routes is

$$\begin{aligned} {A \atopwithdelims ()a_1, a_2, \ldots , a_t} = \frac{A!}{a_1!\, a_2! \cdots a_t!}, \end{aligned}$$

where \(A=\sum _{i=1}^{t} a_i\). The multiplicity of optimal routes is the basis for fault-tolerant routing algorithms, but that is out of the scope of this paper.

Anyway, the best feature of the greedy routing algorithm is perhaps that we don’t need to compute the whole routing vector in advance; we can do it online. However, in that case we lose the multiple routes.

Now, since we are performing addition modulo n, we can relax the requirement that \(s_1 = 1\), provided that \(\gcd (n, s_1, \ldots , s_t) = 1\). If vertex k is not reachable ‘in the first round’, then it will be reachable in some subsequent ‘round’. To the best of our knowledge, there is no study on greedy denomination systems with \(s_1 > 1\). In any case, the requirement that \(s_1 = 1\) is not as restrictive as it looks at first sight, since the circulant \(C(n; s_1, s_2, \ldots , s_t)\), with \(s_1 > 1\), is often isomorphic to a circulant of the form \(C(n; 1, s_2', \ldots , s_t')\).

For example, let \(\Gamma = C(n; S)\), where \(S=\{ s_1, s_2, \ldots , s_t \}\), with \(s_1 > 1\). If there is some \(s_i\) that is relatively prime with n, then by Euler’s theorem, \(s_i^{\phi (n)} \equiv 1 \ (\mod n)\). If \(\lambda \) is relatively prime with n, then \(C(n; \lambda S)\) is isomorphic to \(\Gamma \), where multiplication is taken modulo n. In particular, if we take \(\lambda = s_i^{\phi (n)-1}\), and let \(S' = s_i^{\phi (n)-1} S\), then \(1 \in S'\) and \(\Gamma \cong C(n; S')\). Thus, we can rearrange \(S'\) and we get a circulant graph of the form \(C(n; 1, s_2', \ldots , s_t')\) that is isomorphic to \(\Gamma \).

We can also extend the greedy routing algorithm to the undirected case. Let \(\Gamma \) be a circulant graph \(C(n; \pm s_1, \pm s_2, \ldots , \pm s_t)\), and let \(S^+ = \{ s_1, s_2, \ldots , s_t \}\) and \(S^- = \{ -s_1, -s_2, \ldots , -s_t \}\). Then we can either reduce the routing problem in \(\Gamma \) to the routing problem in the circulant digraph \(\overrightarrow{\Gamma }\), with connection set \(S = S^+ \cup (S^-\mod n)\), or we can restrict the routing problem to the nodes \(k \le \frac{n}{2}\).

4 Analysis of Some Families of Large Circulant Graphs and Digraphs

A classic construction of large directed circulants with small diameter is the one given by Wong and Coppersmith [33]. This construction is the basis for many other variants. More precisely, they proved that the directed circulant \(C(u^t; 1, u, u^2, \ldots , u^{t-1})\) has diameter \(t(u-1)\). We call this construction Family 0. A straightforward consequence of Corollary 1 is that Family 0 is greedy.

A variant of the above construction (Family 1) is given by Hwang [12], namely \(C(u^t-2u; 1, u, u^2, \ldots , u^{t-2}, u^{t-1}-1)\), which has diameter \(t(u-1)-2\). We will prove the following result:

Proposition 1

Family 1 is greedy.

Proof

The subset \(S = \{ 1, u, u^2, \ldots , u^{t-2} \}\) is greedy, hence we only have to check that it remains greedy when we add the generator \(u^{t-1}-1\). This can be done with the aid of the one-point theorem. In this case \(\displaystyle m = \left\lceil \frac{u^{t-1}-1}{u^{t-2}} \right\rceil = u\), hence \(u \cdot u^{t-2} - (u^{t-1}-1) = 1\), and \({\textsc {GreedyCost}}_S(1) = 1 < u\). \(\square \)

Family 1 can be generalized by subtracting \(k \ge 1\) to \(u^{t-1}\), as follows:

Let the Family 1’ of circulants be defined by the set of generators

$$\begin{aligned} S = \big \{ 1, u, u^2, \ldots , u^{t-2}, u^{t-1}-k \big \}, \end{aligned}$$

where \(u \ge 2\), \(t \ge 3\), and the subtract k belongs to a set of integers \(\mathcal {K}\), which depends on u and t. We can distinguish several combinations of u and t, and their corresponding set of subtracts \(\mathcal {K}\), and connection set S:

Case 1::

\(u=2, \ t=3\). This is a trivial case, since S is just \(\{ 1, 2, 4-k \}\), where k is limited to the value 1.

Case 2::

\(u=2, \ t=4\). In this case \(S = \{ 1, 2, 4, 8-k \}\), where \(k \in \mathcal {K}= \{ 1, 2 \}\).

Case 3::

\(u=3, \ t=3\). Here \(S = \{ 1, 3, 9-k \}\), where \(k \in \mathcal {K}= \{ 1, 2, 3, 4 \}\).

Case 4::

\(u=3, \ t=4\). Here \(S = \{ 1, 3, 9, 27-k \}\), where \(k \in \mathcal {K}= \{ 1, 2, 3, 4, 6, 9, 10, 12 \}\).

Case 5::

\(u=2, \ t > 4\). Then \(k \in \mathcal {K}= \{ 1, 2, \ldots , 2u-2 \} \).

Case 6::

\(u=3, \ t > 4\). Then k is in the set \(\mathcal {K}= \{ 1, 2, \ldots , 2u-2, 2u, 2u+1, \ldots , 3u-3 \} \).

Case 7::

All the remaining combinations of u and t, i.e. \(u \ge 4, \ t \ge 3\). Then k is in the set

$$\begin{aligned} \mathcal {K}= \big \{ \;&1, 2, \ldots , 2u-2, \\&2u, 2u+1, \ldots , 3u-3, \\&\vdots \\&(u-1)u \; \big \}, \end{aligned}$$

which corresponds to the upper left triangle of the following matrix (excluding 0), represented in boldface:

$$\begin{aligned} A_{u \times u} = \left[ {\begin{array}{ccccc} 0 &{} \varvec{1} &{} \cdots &{} \varvec{u-2} &{} \varvec{u-1} \\ \varvec{u} &{} \varvec{u+1} &{} \cdots &{} \varvec{2u-2} &{} 2u-1 \\ \varvec{2u} &{} \varvec{2u+1} &{} \cdots &{} 3u-2 &{} 3u-1 \\ \vdots &{} \vdots &{} \ddots &{} \vdots &{} \vdots \\ \varvec{(u-1)u} &{} (u-1)u+1 &{} \cdots &{} u^2-2 &{} u^2-1 \\ \end{array} } \right] \end{aligned}$$

Theorem 2

Family 1’ is greedy.

Proof

Cases \(1-4\) have a (small) finite number of possibilities, and they can be verified by hand, so we can concentrate on the cases \(5-7\). In all those cases \(m=u\), and \(m \cdot u^{t-2} - (u^{t-1}-k) = k\). Let \(\hat{S} = \{ 1, u, u^2, \ldots , u^{t-2} \}\). Note that \({\textsc {GreedyCost}}_{\hat{S}}(k)\) is just the sum of the digits of the representation of k in base u. It is not difficult to verify that

$$\begin{aligned} \big \{ \;&{\textsc {GreedyCost}}_{\hat{S}}(1) = 1, \ldots , {\textsc {GreedyCost}}_{\hat{S}}(2u-2) = u-1, \\&{\textsc {GreedyCost}}_{\hat{S}}(2u) = 2, \ldots , {\textsc {GreedyCost}}_{\hat{S}}(3u-3) = u-1, \\&\vdots \\&{\textsc {GreedyCost}}_{\hat{S}}((u-1)u) = u-1 \; \big \}. \end{aligned}$$

\(\square \)

Hwang also proposed another family of greedy circulants (Family 2), defined as

$$\begin{aligned} C(U^{(t)} ; 1, u_1, u_1 u_2, \ldots , U^{(t-1)}), \end{aligned}$$

where \(U^{(k)} = \prod _{i=1}^{k} u_i\). The diameter of Family 2 is \(\sum \nolimits _{i=1}^{t} (u_i-1)\). It is clear that Family 2 is greedy by Corollary 1. Family 2 can also be generalized in the same manner as Families 1 and 1’, but there are more cases to consider, and the proof becomes a bit cumbersome.

In [5], Chang and Chen introduce several families of triple-loop networks that improve on the previous constructions. Among these we have:Footnote 1

Family 3: \(C(w^3-6w^2+12w-8 ; 1, w, w^2-3w+2)\), of diameter \(3w-11\) (Theorem 5 of [5]).

Family 4: \(C(w^3-7w^2+14w-11 ; 1, w, w^2-4w+2)\), of diameter \(3w-13\) (Theorem 6 of [5]).

Proposition 2

Family 3 and Family 4 are not greedy.

Proof

Family 3: The subset \(S = \{ 1, w \}\) is greedy, hence we only have to check whether it remains greedy when we add the third generator, \(w^2-3w+2\). In this case \(m = w-2\), hence \((w-2)w - (w^2-3w+2) = w-2\), and \({\textsc {GreedyCost}}_S(w-2) = w-2 = m\).

Family 4: The subset \(S = \{ 1, w \}\) is greedy, hence we only have to check whether it remains greedy when we add the third generator, \(w^2-4w+2\). In this case \(m = w-3\), hence \((w-3)w - (w^2-4w+2) = w-2\), and \({\textsc {GreedyCost}}_S(w-2) = w-2 > m\). \(\square \)

Negative results, like that of Proposition 2, seem to be quite abundant, so we will not review any more examples. Instead, we will extend these ideas to infinite sequences.

5 Totally Greedy Sets and Totally Greedy Sequences

A set \(S = \{ 1, s_2, \ldots , s_t \}\) is totally greedyFootnote 2 if every prefix subset \(\{ 1, s_2, \ldots , s_k \}\), with \(k \le t\) is greedy. Obviously, a totally greedy set is also greedy, but the converse is not true in general. Take, for instance, the greedy set \(\{ 1, 2, 5, 6, 10 \}\), whose prefix subset \(\{ 1, 2, 5, 6 \}\) is not greedy.

The definition of totally greedy sets can be extended to infinite sequences in an obvious way. We can now use Theorem 1 to prove that some noteworthy sequences are totally greedy:

Proposition 3

The (modified) Fibonacci sequence \(\{ 1, 2, 3, 5, 8, \ldots \}\) is totally greedy.

Proof

Let \(F^{(t)} = \{ 1, 2, 3, \ldots , F_t \}\) be the set of the first t Fibonacci numbers (not counting \(F_0\)), for \(t \ge 1\). We will prove by induction that any \(F^{(t)}\) is greedy. It is clear that \(F^{(1)}\) and \(F^{(2)}\) are greedy, and it is very easy to verify that \(F^{(3)}\) is also greedy. So, let’s suppose that \(F^{(t)}\) for \(t \ge 3\) is greedy, and let’s prove that \(F^{(t+1)}\) is also greedy.

So, in this case \(\displaystyle m = \left\lceil \frac{F_{t+1}}{F_{t}} \right\rceil = \left\lceil 1+\frac{F_{t-1}}{F_{t}} \right\rceil = 2\), hence \(2 \cdot F_t - F_{t+1} = F_t - F_{t-1} = F_{t-2}\), and \({\textsc {GreedyCost}}_{F^{(t)}}(F_{t-2}) = 1 < 2 = m\). \(\square \)

A similar result holds for the Lucas numbers, which are defined by the same recurrence \(L_k = L_{k-1} + L_{k-2}\), but with the initial values \(L_0 = 2\) and \(L_1 = 1\) (Sequence A000032 of [24]). In this case we can rearrange the sequence so that it starts with 1, as follows: \(\{ 1, 2, 3, 4, 7, 11, 18, 29, \ldots \}\). Actually, we can easily generalize Proposition 3 to a family of sequences defined by the recurrence

$$\begin{aligned} G_k = p G_{k-1} + G_{k-2}, \end{aligned}$$
(8)

where \(p \ge 1\) is an integer. This family includes the Fibonacci and Lucas numbers, where \(p=1\), and other interesting number sequences, such as the Pell numbers, where \(p=2\) (Sequence A000129 of [24]). For the moment we will fix \(G_0 = 0\) and \(G_1 = 1\), as in the Fibonacci and Pell numbers, although it is not difficult to extend this result to other combinations of \(G_0\) and \(G_1\).

Theorem 3

The sequence defined by \(G_0 = 0, \, G_1 = 1\), and Eq. (8), is totally greedy for all \(p \ge 1\).

Proof

For the purposes of this theorem we leave \(G_0\) out, so that the sequence starts with 1. So, let \(t \ge 1\), and let \(G^{(t)} = \{ 1, p, p^2+1, \ldots , G_t \}\) be the set of the first t generalized Fibonacci numbers defined by the recurrence 8. As before, we will prove the theorem by induction. For the base case we have to verify that \(G^{(3)}\) is greedy, given that \(G^{(2)}\) is greedy. Indeed we have: \(\displaystyle m = \left\lceil \frac{G_{3}}{G_{2}} \right\rceil = \left\lceil p + \frac{1}{p} \right\rceil = p+1\). Now, \(m G_{2} - G_{3} = (p+1)p-(p^2+1) = p-1\), and \({\textsc {GreedyCost}}_{G^{(2)}}\left( p-1 \right) = p-1 < p+1 = m\).

So, let’s suppose that \(G^{(t)}\) is greedy for some arbitrary \(t \ge 3\), and let’s prove that \(G^{(t+1)}\) is also greedy.

We have \(\displaystyle m = \left\lceil \frac{G_{t+1}}{G_{t}} \right\rceil = \left\lceil p + \frac{G_{t-1}}{G_{t}} \right\rceil = p+1\). Now, \((p+1) G_t - G_{t+1} = G_t - G_{t-1} = (p-1) G_{t-1} + G_{t-2}\), whence \({\textsc {GreedyCost}}_{G^{(t)}}\left( (p-1) G_{t-1} + G_{t-2} \right) = p < p+1 = m\). \(\square \)

Tribonacci numbers are another natural generalization of Fibonacci numbers. Tribonacci numbers are defined by the third-order recurrence

$$\begin{aligned} T_k = T_{k-1} + T_{k-2} + T_{k-3}. \end{aligned}$$
(9)

Different choices of \(T_1\), \(T_2\) and \(T_3\) lead to different sequences, hence we may speak about the family of Tribonacci sequences. For instance, if we take \(T_1 = T_2 = 0\) and \(T_3 = 1\) we get the sequence \(\{ 1, 2, 4, 7, 13, 24, 44, 81, \ldots \}\) (sequence A000073 of [24]). On the other hand, if we take \(T_1 = T_2 = T_3 = 1\) we get the sequence \(\{ 1, 3, 5, 9, 17, 31, 57, 105, \ldots \}\) (sequence A000213 of [24]). Finally, by taking \(T_1 = T_3 = 0\) and \(T_2 = 1\) we get the sequence \(\{ 1, 2, 3, 6, 11, 20, 37, 68, \ldots \}\) (sequence A001590 of [24]). Note that the original Tribonacci sequences have been shifted here, so that they start at the last occurrence of 1.

Theorem 4

Let \(\{ \mathcal {T}_n \}_{n \in \mathbb {N}}\) be a sequence generated by the recurrence

$$\begin{aligned} \mathcal {T}_k = \mathcal {T}_{k-1} + \mathcal {T}_{k-2} + \mathcal {T}_{k-3}, \end{aligned}$$
(10)

with initial values \(1 = \mathcal {T}_1< \mathcal {T}_2 < T_3\). If the set \(\mathcal {T}^{(4)} = \{ \mathcal {T}_1, \mathcal {T}_2, \mathcal {T}_3, \mathcal {T}_4 \}\) is greedy, then the Tribonacci sequence \(\{ \mathcal {T}_n \}_{n \in \mathbb {N}}\) is totally greedy.

Proof

Again, we prove the theorem by induction. The base case is guaranteed by the assumptions of the theorem. So, let’s suppose that \(\mathcal {T}^{(k)}\) is totally greedy for some arbitrary \(k \ge 3\), and let’s prove that \(\mathcal {T}^{(k+1)}\) is also greedy (and hence totally greedy).

We have \(\displaystyle m = \left\lceil \frac{\mathcal {T}_{k+1}}{\mathcal {T}_{k}} \right\rceil = \left\lceil 1+\frac{\mathcal {T}_{k-1} + \mathcal {T}_{k-2}}{\mathcal {T}_{k}} \right\rceil = 2\), hence \(2 \cdot \mathcal {T}_k - \mathcal {T}_{k+1} = \mathcal {T}_{k-3}\), and \({\textsc {GreedyCost}}_{\mathcal {T}^{(k)}}(\mathcal {T}_{k-3}) = 1 < 2 = m\). \(\square \)

Theorem 4 applies to the three sequences, A000073, A000213 and A001590, mentioned above.

6 Some Large Greedy Circulant Networks

Research in the Degree/Diameter Problem has been greatly enhanced by the compilation of the largest known graphs. In [28] there is a list of graph categories, with the corresponding tables of largest known graphs for each combination of degree and diameter. These tables provide benchmarks that can be used to compare different constructions and algorithms. In particular, there is a table for the largest known undirected circulant graphs [29], that spans degrees 3–20 and diameters 2–16.

Collecting the largest known graphs of a specific class is an arduous task. As of today, there is still no such compilation of the largest circulant digraphs, although there are several papers that provide computational results. In this section, we also summarize some preliminary computational results, that could lead to a compilation of the largest greedy circulant graphs and digraphs in the near future.

Our starting point are Families 0, 1 and 2, described in Sect. 4, as well as the tables of largest circulant graphs and digraphs (some of them greedy) given in [6]. Another source is a table given in [26], where some efficient greedy sets are given. The efficiency of those sets is measured in terms of the average greedy cost. In our circulant graph setting, this corresponds to the average distance. On the other hand, the diameter of a circulant graph with such a given connection set is the largest greedy cost. The diameter and the average distance must not always coincide, i.e. the connection set that minimizes the average distance is not necessarily the same connection set that minimizes the diameter. However, both measures are intimately related, and they often coincide.

We have summarized our findings in Tables 3 and 4. For each combination of outdegree \(3 \le d \le 6\) (degree \(5 \le \Delta \le 6\)) and diameter \(2 \le k \le 10\) (undirected diameter \(2 \le D \le 10\)), we give the order of the largest greedy circulant digraph (graph) found so far, together with the connection set that realizes it. Note that connection sets of the form \(\{ 1, s_2 \}\) are always greedy, hence the corresponding circulant digraphs of outdegree 2, and the undirected circulant graphs of degrees 3 and 4, have already been tabulated in previous works.

In principle, we may also construct greedy circulant graphs and digraphs from any totally greedy sequence, such as the Fibonacci, Lucas, and Tribonacci sequences mentioned in Sect. 5. For the sake of illustration we list the largest digraphs and graphs generated by prefixes of the Fibonacci sequence in Tables 1 and 2, respectively. However, as it can be seen, the graphs that are obtained from those sequences fall short of the benchmarks recorded in Tables 3 and 4.

7 Some Open Problems

The purpose of this paper was not to make a complete catalogue of greedy and non-greedy families of circulant networks proposed in the literature. However, such a catalogue might be handy for network designers. In particular, it could be interesting to investigate the families that include some the largest known circulant graphs for some combinations of degree and diameter, such as the families described in [13, 14].

The largest known circulant graphs are tabulated in [29] for each combination of degree and diameter. It would be natural to ask for the construction of a similar table of the largest known greedy circulants.

Another issue here is to investigate the greediness of connection sets of the form \(S=\{ s_1, s_2, \ldots , s_t \}\), with \(s_1 > 1\), especially in those cases where the circulant \(C(n; s_1, s_2, \ldots , s_t)\) is not isomorphic to a circulant of the form \(C(n; 1, s_2', \ldots , s_t')\). In this case, not all integers are representable as a sum of the elements of S, but we can investigate the optimality of the greedy algorithm for the integers that are indeed representable, i.e. the sub-monoid \(\langle S \rangle \subseteq \mathbb {N}\) generated by S. Nevertheless, in the context of circulant graphs, since we are demanding that \(\gcd (n, s_1, \ldots , s_t) = 1\), all the integers will be representable modulo n.

In the more general setting of numerical semigroups, it could be interesting to investigate the properties of numerical semigroups generated by greedy sets.