Electronic Journal of Graph Theory and Applications 13 .
, 75Ae89 On arrowhead and diamond diameters Dominique DeAseArable National Institute of Applied Sciences.
Rennes.
France domidese@gmail.
Abstract Arrowhead and diamond form a family of two hierarchical Cayley graphs defined on the triangular In their undirected version, they are isomorphic and merely define two distinct representations of the same graph.
This paper gives the expression of their diameter, in the oriented and nonAe oriented case.
It also displays the full distribution of antipodals.
This family could appear as a promising topology for NetworkAeonAeChip architectures.
Keywords: Cayley graphs, interconnection networks.
NoC, diameters, arrowhead & diamond Mathematics Subject Classification : 05C12, 05C60, 68M10 DOI: 10.
5614/ejgta.
Introduction Networks are represented by graphs or digraphs: a vertex in the graph stands for a node in the network while an edge .
an ar.
stands for a fullAeduplex .
halfAeduple.
communication link.
The paper is concerned with a family of tori .
arrowhead and diamon.
which was defined on the triangular .
r AuhexavalentA.
Their related interconnection networks have several important advantages.
They have a bounded degree and the highest allowed degree for a twoAedimensional regular grid.
They are good hosts for embedding the normal grid.
As hierarchical Cayley graphs, they allow recursive constructions and divideAeandAeconquer schemes for information dissemination like broadcasting and gossiping .
Ae.
They could accordingly provide a promising topology for NetworkAeonAeChip AuNoCAy architectures, once the AudiagonalAy link be suitable for onAedie implementation .
Ae.
Received: 25 February 2020.
Revised: 11 December 2024.
Accepted: 8 March 2025.
On arrowhead and diamond diameters DeAseArable In general, the topologies related to plane tessellations belong to the family of multiAeloop Ae or circulant Ae networks .
The usual trend for twoAedimensional hexavalent networks is a hexagonal torus HD with D circular rings of length 6D arranged around a central node, the order of HD is the centered hexagonal1 number ND = 3D2 3D 1 and D is the diameter of HD .
Incidentally, this family of AuhoneycombsAy HD was encountered elsewhere, arising in various projects such as FAIMAe1 .
Mayfly .
and HARTS .
It was the era of microcomputers, the era of networks of microcomputers organized into clusters and the era of the famous Cosmic Cube .
Eventually, this HD family emerged more recently with the AuEJAy .
s EiseinsteinAeJacob.
On the wrong side, those circulant tilings are not easily scalable, as their respective OEIS sequence can attest.
Indeed, they are Cayley graphs .
graphs of group.
so they are regular but this property is not enough to fulfill our request for scalability.
Scalability is a powerful feature for generalAepurpose computers and interconnection networks.
This property allows divideAeandAe conquer strategies both for construction methods and for problemAesolving methods.
This is why another approach is addressed hereafter.
The topology of our arrowhead family .
is quite different.
The construction follows a recursive scheme and yields various representations of .
digraphs or .
graphs, either as SierpinAskiAelike arrowhead 2 or hexagonal hexarrowhead or either as lozenged diamond or square orthodiamond.
The construction of arrowheads and diamonds, not isomorphic as digraphs, is induced by two possible orientations in the hexavalent lattice.
In their undirected version, they are isomorphic and merely define two distinct representations of the same graph.
So far, the hexarrowhead underlies a cellular automata network used in the area of geomechanics as a framework to study the consistency of the model with the behavior of granular matter .
Ae.
It was also applied to study its suitability for scale change in physical systems .
Besides, the orthodiamond, named AuTn Ay therein, is the subject of several works on cellular multiagent systems .
Ae.
: routing performances are compared with a subnetwork of Tn which is just the 2n Aeary 2Aecube .
It is worth pointing out that another family of AuaugmentedAy kAeary 2Aecubes was investigated elsewhere .
for any k but which coincide with Tn only when k = 2n .
As far as we are concerned and in order to preserve the morphism properties between arrowhead and diamond, that value k = 2n is mandatory.
Oriented and nonAeoriented diameters are important parameters that define the maximum distance from any vertex to another in digraphs and graphs and they provide lower bounds for routing and global communications.
This paper is devoted to their study in the arrowhead family and yields their exact value as well as the full distribution of antipodals.
In Sect.
2, we recall some general statement concerning Cayley graphs and arrowhead and diamond are redefined from .
Section 3 and Section 4 are devoted to the analysis of the distribution of the antipodals and the computation of the diameter, respectively for the undirected and the directed version of these graphs.
A preliminary version of this paper has been published elsewhere .
Sequence A003215 in the OEIS: 1, 7, 19, 37, 61, 91.
Ai The OnAeLine Encyclopedia of Integer Sequences.
We borrow the term AuarrowheadAy from Mandelbrot .
about one of the SierpinAskiAos fractal constructions.
On arrowhead and diamond diameters DeAseArable Arrowhead and Diamond A Cayley graph or digraph e(G.
S) is constructed from a group G and a generating set S OO G.
The vertex set is G and the edge set G y S.
Cayley graphs .
he same remarks hold for digraph.
are regular of degree | S |.
Their edgeAeconnectivity .
he minimum number of edges whose removal disconnects the grap.
satisfies = | S |.
They are vertexAetransitive .
r vertexAesymmetri.
in the sense that for any pair .
, uA ) of vertices there exists an automorphism of e that maps u into uA .
Definition 2.
Given the group Gn = Z2n y Z2n with n OO N :
Ie A We define the directed arrowhead AT n = e (Gn .
S ) as the digraph of Gn with the generating set S = .
1 , s2 , s3 ) = ((Oe1.
Oe.
, .
, .
, .
, .
A Let S Oe = (Oes1 .
Oes2 .
Oes3 ) be the set of inverses of S and let the generating set S = S OS Oe now closed under inverses.
We define the undirected arrowhead as AT n = e (Gn .
S).
Ie A We define the directed diamond DT n = e (Gn .
T ) as the digraph of Gn with the generating set T = .
1 , t2 , t3 ) = (Oes1 , s2 , s3 ) = (.
, .
, .
, .
, .
, .
A Let T Oe = (Oet1 .
Oet2 .
Oet3 ) be the set of inverses of T and let the generating set T = T OT Oe now closed under inverses.
We define the undirected diamond as DT n = e (Gn .
T ).
A DT n and AT n are isomorphic since T = S.
The order of these graphs is given by N = | Gn | = 4n and the number of arcs .
r edge.
by | S || Gn | = 3N.
In the sequel, the detection of antipodals and the computation of diameters will follow an inductive scheme.
It is therefore convenient to exploit the recursive structure of the graphs as follows.
Definition 2.
Let 0 O k O n and let again Gn = {( x, y ) = xs2 ys3 | x, y OO Z2n } .
be the vertex set expressed from the previous definition and let Gn,k = 2k A GnOek = {( 2k x, 2k y ) | x, y OO Z2nOek } .
be the subgroup of Gn generated by 2k S = { 2k s | s OO S }.
Ie Ie We define AT n,k = e (Gn,k , 2k S ) isomorphic to AT nOek as the digraph of Gn,k with the generating set 2k S .
Ie Ie As a matter of fact, this statement gives an embedding scheme of AT nOek into AT n with dilation Ie A definition of digraph DT n,k and of their undirected counterpart will follow from a similar On arrowhead and diamond diameters DeAseArable Figure 1.
Representation of T1 and T2 Ae some vertices are replicated for convenience.
In the following, the undirected AeisomorphicAe graphs AT n and DT n will be denoted as Tn .
The representation of T1 and T2 is displayed in Fig.
T0 is not displayed, reduced to the single vertex of G0 = {.
, .
} as a 6Aevalent vertex.
It should be observed in .
that Gn,0 = Gn and Gn,n = G0 .
In T1 we observe that G1,0 = G1 = {.
, .
, .
, .
, .
, .
, .
, .
} with 4 vertices and that G1,1 = 2A G0 = {.
, .
In T2 one get G2 = {( x, y ) = xs2 ys3 | x, y OO Z4 } with 16 vertices and see that G2,1 = 2A G1 = {.
, .
, .
, .
, .
, .
, .
, .
} isomorphic to G1 and that G2,2 = 4A G0 = {.
, .
NonAeOriented Diameter The diameter of a graph is the maximum distance between any pair of vertices.
We call AuorientedAy .
AunonAeorientedA.
the diameter of a directed .
Two vertices are said to be antipodal if their distance is the diameter.
Without loss of generality, we can compute the diameter as the length of the shortest path from the AuoriginAy .
, .
to an antipodal since the graphs are vertexAetransitive.
Hereafter, the term AuantipodalAy will be viewed from that vertex.
Diameter in Tn In Fig.
1, it appears as trivial that vertices in subset {.
, .
, .
, .
, .
, .
} in T1 are antipodal and at distance 1.
We claim that in T2 the subset {.
, .
, .
, .
, .
, .
} as well as its symmetric part {.
, .
, .
, .
, .
, .
} are antipodal at distance 2.
To sketch the proof, let us fix x O y and then extend to the triangular diagrams in Fig.
Beforehand we give the following definitions.
Definition 3.
Herein, for n > 0, the ordered subset En will always denote an antipodal 3Aecycle in Tn and En,1 will denote the image of EnOe1 whereas En,2 will denote the image of EnOe1,1 under the mapping induced by .
Thus we have On arrowhead and diamond diameters DeAseArable Figure 2.
Triangular diagram of T2 and T1 .
Induction from T1 to T2 .
Resulting shortest paths to antipodals in T2 .
A E0 = {.
, .
A E1 = (.
, .
, .
, .
, .
, .
A En,1 = 2AEnOe1 = {( 2x, 2y ) | x, y OO EnOe1 } .
> .
A En,2 = 2AEnOe1,1 = {( 2x, 2y ) | x, y OO EnOe1,1 } = 4AEnOe2 .
> .
In the sequel, the term image will always mean the image under the isomorphic mapping in Def.
Note that any En,k is a subset of Gn,k .
In the diagrams of Fig.
2 and further, the vertices of those different subsets will be labeled as follows:
A En = (An .
Bn .
Cn ) A En,1 = (An,1 .
Bn,1 .
Cn,1 ) A En,2 = (An,2 .
Bn,2 .
Cn,2 ).
Lemma 3.
Let Dn be the nonAeoriented diameter of Tn .
Then D0 = 0 and Dn = 2DnOe1 1 or Dn = 2DnOe1 depending upon the oddAeeven parity of n.
Proof : We prove by induction and refer first to Fig.
For the base case n = 1 the vertices of E1,1 coincide as origin at distance 0 and vertex set E1 is trivially antipodal at distance D1 = For n = 2, vertex set E2,2 as image of E1,1 coincide as origin at distance 0.
Now, vertices .
A2 , a2 ), .
A2 , bAA2 ), .
A2 , cAA2 ) reachable from (A2,2 .
B2,2 .
C2,2 ) are at distance 1 and then the triple (A2 .
B2 .
C2 ) is at distance 2.
Besides, vertices of E2,1 as image of E1 are by induction at distance 2D1 = 2.
Therefore the triple E2 is antipodal, as well as E2,1 and at distance the diameter D2 = 2.
On arrowhead and diamond diameters DeAseArable Figure 3.
Triangular diagrams in Tn Ae for n odd (I.
Ae for n even (I.
On arrowhead and diamond diameters DeAseArable A n odd: Let En,1 and En,2 be the respective images of EnOe1 and EnOe1,1 in upper Fig.
From induction, vertices of those both triples are assumed at distance 2DnOe1 .
Now the six vertices .
An , an ), .
An , bAAn ), .
An , cAAn ) are also at distance 2DnOe1 : aAn and An,2 are reachable from a common antecedent ( xaAn , yaAn ) t2 = ( xAn,2 , yAn,2 ) t1 and idem for aAn and Cn,1 ( xaAn , yaAn ) t1 = ( xCn,1 , yCn,1 ) t2 and so forth.
Therefore those six vertices are at distance 2DnOe1 .
Vertex An can then be reached through .
An , an ).
Bn through .
An , bAAn ).
Cn through .
An , cAAn ).
The triple (An .
Bn .
Cn ) can also be reached from (Bn,1 .
Cn,1 ), (Cn,1 .
An,1 ), (An,1 .
Bn,1 ).
It is therefore antipodal, at distance the diameter Dn = 2DnOe1 1.
A n even: Let En,2 be the image of EnOe1,1 in lower Fig.
3 and, from induction, with vertices assumed at distance 2(DnOe1 Oe .
The three pairs .
An , an ), .
An , bAAn ), .
An , cAAn ) reachable from (An,2 .
Bn,2 .
Cn,2 ) are at distance 2(DnOe1 Oe .
1 = 2DnOe1 Oe 1.
Vertex An can be reached through .
An , an ).
Bn through .
An , bAAn ).
Cn through .
An , cAAn ) and then the triple (An .
Bn .
Cn ) is at distance .
DnOe1 Oe .
1 = 2DnOe1 .
Besides.
En,1 as image of EnOe1 has also its vertices at distance 2DnOe1 .
Therefore the triple (An .
Bn .
Cn ) is antipodal, as well as (An,1 .
Bn,1 .
Cn,1 ) and at distance the diameter Dn = 2DnOe1 .
Lemma 3.
Two useful relations are exhibited.
OAn > 0 : DnOe1 Dn = 2n Oe 1 OAn > 1 : Dn Oe DnOe2 = 2nOe1 Proof : Let us rewrite Dn = 2DnOe1 An from Lemma 3.
1 where An O n .
Given un = DnOe1 Dn we note that u1 = 1 and show that un 1 = 2un 1.
Now un 1 = Dn Dn 1 = .
DnOe1 An ) .
Dn An 1 ) but An An 1 = 1 for any n whence un 1 = 2un 1 and .
results from an obvious induction.
For .
we note from above that Dn Oe DnOe2 = un Oe unOe1 = 2nOe1 .
Proposition 3.
Tn has the diameter Oo Oo 2 ( N Oe .
2 N Oe1 Dn = or Dn = depending on the oddAeeven parity of n.
On arrowhead and diamond diameters DeAseArable Proof : Follows from Lemma 3.
For n odd.
Dn = 2DnOe1 1 and by .
DnOe1 = .
n Oe .
Oe Dn whence 3Dn = 2 A 2n Oe 1.
For n even.
Dn = 2DnOe1 whence 3Dn = 2 A .
n Oe .
The ten first values of Tn diameter are displayed below.
4096 16384 65536 262144
Antipodals in Tn Some relevant properties of antipodal coordinates are highlighted hereafter and antipodals are enumerated.
Proposition 3.
The antipodal coordinates in En satisfy:
A n odd: ( xCn , yCn ) = ( DnOe1 .
Dn ) A n even: ( xBn , yBn ) = ( DnOe1 .
Dn ).
Proof : This is true for n = 1 where ( xC1 , yC1 ) = .
, .
= ( D0 .
D1 ) and for n = 2 where ( xB2 , yB2 ) = .
, .
= ( D1 .
D2 ) referring back to Fig.
1 and Fig.
A n odd .
pper Fig.
: assume ( xBnOe1 , yBnOe1 ) = ( DnOe2 .
DnOe1 ).
Then ( xBn,1 , yBn,1 ) = ( 2DnOe2 , 2DnOe1 ) = ( DnOe1 .
Dn Oe .
since n Oe 1 is even when n is odd, whence ( xCn , yCn ) = ( xBn,1 , yBn,1 ) .
, .
A n even .
ower Fig.
: assume ( xCnOe1 , yCnOe1 ) = ( DnOe2 .
DnOe1 ).
Then ( xCn,1 , yCn,1 ) = ( 2DnOe2 , 2DnOe1 ) = ( DnOe1 Oe 1.
Dn ) since n Oe 1 is odd when n is even, whence ( xBn , yBn ) = ( xCn,1 , yCn,1 ) .
, .
Coordinates of other antipodals are simply deduced.
Referring back to Fig.
1 we now focus on the subset {.
, .
, .
, .
, .
, .
}, antipodal by symmetry.
By fixing x Ou y and as from Def.
1 we define the symmetric subsets A En = (An .
B n .
C n ) A En,1 = (An,1 .
B n,1 .
C n,1 ) A En,2 = (An,2 .
B n,2 .
C n,2 ) where ( xAn , yAn ) = ( OexAn .
OeyAn ) and where any vertex in those subsets is defined in that way.
Proposition 3.
The antipodal coordinates in En satisfy:
A n odd: ( xB n , yB n ) = ( Dn .
DnOe1 ) A n even: ( xC n , yC n ) = ( Dn .
DnOe1 ).
On arrowhead and diamond diameters DeAseArable Figure 4.
Antipodal coordinates in Tn Ae for n odd (I.
Ae for n even (I.
Figure 5.
Antipodal inverses in Tn Ae for n odd (I.
Ae for n even (I.
On arrowhead and diamond diameters DeAseArable Proof : From Proposition 3.
2 and Fig.
A n odd: ( xBn , yBn ) = ( xCn , yCn ) .
, .
whence ( xB n , yB n ) = ( OeDnOe1 Oe 1.
OeDn Oe 1 ) and .
yields ( xB n , yB n ) = ( Dn .
DnOe1 ) by a simple reduction in Z2n .
A n even: ( xCn , yCn ) = ( xBn , yBn ) .
, .
whence ( xC n , yC n ) = ( OeDnOe1 Oe 1.
OeDn Oe 1 ) whence again the result.
Corollary 3.
The antipodal inverses satisfy for any n:
A ( xAn , yAn ) = ( yAn , xAn ) A ( xB n , yB n ) = ( yCn , xCn ) A ( xC n , yC n ) = ( yBn , xBn ) Coordinates of other antipodals subsets are simply deduced.
Corollary 3.
Let NA,n be the number of antipodals in Tn .
Then A NA,1 = | E1 O E1 | = | E1 | = 3
A NA,2 = | E2 O E2 | | E2,1 O E2,1 | = | E2 O E2 | | E2,1 | = 9
| En O En | = 6 A NA,n = | En O En | | En,1 O En,1 | = 12 depending on the oddAeeven parity of n > 2.
We observe that E1 and E1 coincide and that E2,1 and E2,1 coincide.
Oriented Diameter Ie Diameter and Antipodals in AT n Ie We now refer to digraph AT n in Def.
1 with its generating set S highlighted in the inset of Ie Fig.
Again it appears as trivial that vertices in subset {.
, .
, .
, .
, .
, .
} in AT 1 are antipodal Ie and at distance 1 from the origin .
, .
We claim that in AT 2 the subset {.
, .
, .
, .
, .
, .
} as well as its symmetric part {.
, .
, .
, .
, .
, .
} are antipodal at distance 3.
To sketch the proof, let us again fix x O y and then extend to the triangular diagrams in Fig.
Ie E n be the oriented diameter of AT n .
Then D E 0 = 0 and D E n = 2D E nOe1 1 for Lemma 4.
Let D n > 0.
On arrowhead and diamond diameters Ie DeAseArable Ie Figure 6.
Orientation in AT 1 and AT 2 Ae orientation highlighted in the inset.
Ie E 0 = 0 and in AT 1 the triple (A1 .
B1 .
C1 ) = (.
, .
, .
, .
, .
, .
) is clearly antipodal and Proof : D E 1 = 1.
Let An,2 be the image of AnOe1,1 whatever the parity of n, and assumed from induction at E nOe1 Oe .
There exists a directed path distance 2(D ( An,2 Ie aAn Ie an Ie An ) E nOe1 Oe .
3 = 2D E nOe1 1.
Idem for of length 3 from An,2 to An therefore An is at distance 2(D ( Bn,2 Ie Bn ) and ( Cn,2 Ie Cn ).
E nOe1 Besides the triple ( An,1 .
Bn,1 .
Cn,1 ) as image of ( AnOe1 .
BnOe1 .
CnOe1 ) is at distance 2D by induction.
The triple (An .
Bn .
Cn ) is then also reachable either from ( Cn,1 .
An,1 .
Bn,1 ) for n odd or from ( Bn,1 .
Cn,1 .
An,1 ) for n even.
It is therefore antipodal and at distance the diameter E n = 2D E nOe1 1.
Ie Oo E n = N Oe 1 and the number of antipodals Proposition 4.
AT n has the diameter D A NA,1 E = | E1 O E1 | = | E1 | = 3 A NA,n = | En O En | = 6 > .
Ie Diameter and Antipodals in DT n Ie We now refer to digraph DT n with its generating set T = .
1 , t2 , t3 ) = (.
, .
, .
, .
, .
, .
) in Def.
Ie Oo E n = N Oe 1 and the number of antipodals Proposition 4.
DT n has the diameter D Oo A ND,n = 2 N Oe 1 for any n OO N.
Proof : The proof here is rather trivial: there is 1 vertex at distance 0, there are 3 vertices at distance 1, there are 2p 1 vertices at distance p and therefore 2.
n Oe .
1 = 2n 1 Oe 1 vertices at distance 2n Oe 1.
On arrowhead and diamond diameters DeAseArable Ie Figure 7.
Triangular diagrams in AT n Ae for n odd (I.
Ae for n even (I.
On arrowhead and diamond diameters DeAseArable Conclusion Arrowhead and diamond form a family of two hierarchical Cayley graphs defined on the triangular In their undirected version, they are isomorphic and merely define two distinct representations of the same graph.
This paper gives the exact expression of their diameter, in the oriented and nonAe oriented case as well as the full distribution of antipodals.
This family of Cayley graphs could appear as a promising topology for NetworkAeonAeChip AuNoCAy architectures.
To our knowledge, we have no trace of this topology in the field of NoC and this lack would open an immense challenge.
A possible hindrance could be the fulfillment of wires at angles other than the common angles .
A/.
Ae namely either A/4 for the orthodiamond or kA/3 for the hexarrowhead, even if some achievements seem to deny this intricacy .
, .
Prototyping simulations will be planned in the near future.
Acknowledgement I am very grateful towards a reviewer of an ancient version of this article and who suggested a complete redefinition of the graphs presented a first time in .
, a redefinition which greatly supported the elaboration of this article.
References