# Mathematical Properties of the Hyperbolicity of Circulant Networks

Authors: Juan C. Hernández; José M. Rodríguez; José M. Sigarreta
Journal: Advances in Mathematical Physics
 (2015)

---

## Abstract

IfX is a geodesic metric space and x1,x2,x3∈X, a geodesic triangle
T={x1,x2,x3} is the union of the three geodesics [x1x2], [x2x3], and [x3x1] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. The study of the hyperbolicity constant in networks is usually a very difficult task; therefore, it is interesting to find bounds for particular classes of graphs. A network is circulant if it has a cyclic group of automorphisms that includes an automorphism taking any vertex to any other vertex. In this paper we obtain several sharp inequalities for the hyperbolicity constant of circulant networks; in some cases we characterize the graphs for which the equality is attained.


---

## Body

## 1. Introduction

The first works on Gromov hyperbolic spaces deal with finitely generated groups (see [1]). Initially, Gromov spaces were applied to the study of automatic groups in the science of computation (see, e.g., [2]); indeed, hyperbolic groups are strongly geodesically automatic; that is, there is an automatic structure on the group [3]. Besides, hierarchical networks have been found to have “hidden hyperbolic structure” [4]. For a study of other parameters in complex networks, see [5]. The concept of hyperbolicity appears also in discrete mathematics, algorithms, and networking. For example, it has been shown empirically in [6] that the Internet topology embeds with better accuracy into a hyperbolic space than into an Euclidean space of comparable dimension; the same holds for many complex networks; see [7]. A few algorithmic problems in hyperbolic spaces and hyperbolic graphs have been considered in recent papers (see [8]). Another important application of these spaces is the study of the spread of viruses on the Internet (see [9]). Furthermore, hyperbolic spaces are useful in secure transmission of information on the network (see [9]). The study of Gromov hyperbolic networks is a subject of increasing interest (see, e.g., [7, 9–20] and the references therein).Hyperbolic spaces play an important role in geometric group theory and in the geometry of negatively curved spaces (see [1, 21]). The concept of Gromov hyperbolicity grasps the essence of negatively curved spaces like the classical hyperbolic space, Riemannian manifolds of negative sectional curvature bounded away from 0 and of discrete spaces like trees and the Cayley graphs of many finitely generated groups. It is remarkable that a simple concept leads to such a rich general theory (see [1, 21]).Ifγ:[a,b]→X is a continuous curve in a metric space (X,d), thelength of γ is defined as (1)Lγ≔sup⁡∑i=1ndγti-1,γti:a=t0<t1<⋯<tn=b. We say that γ is ageodesic if we have L(γ|t,s)=d(γt,γ(s))=|t-s| for every s,t∈[a,b] (then γ is equipped with an arc-length parametrization). The metric space X is said to begeodesic if for every couple of points in X there exists a geodesic joining them; we denote by [xy] any geodesic joining x and y; this notation is ambiguous, since in general we do not have uniqueness of geodesics, but it is very convenient. Consequently, any geodesic metric space is connected. If the metric space X is a network, then the edge joining the vertices u and v will be denoted by [u,v].Along the paper we just consider graphs with every edge of length1. In order to consider a network G as a geodesic metric space, identify (by an isometry) any edge [u,v]∈E(G) with the interval [0,1] in the real line; then the edge [u,v] (considered as a graph with just one edge) is isometric to the interval [0,1]. Thus, the points in G are the vertices and, also, the points in the interior of any edge of G. In this way, any connected network G has a natural distance defined on its points, induced by taking the shortest paths in G, and we can see G as a metric graph. If x,y are in different connected components of G, we define dG(x,y)=∞. Throughout this paper, G=(V,E) denotes a simple (without loops and multiple edges) graph (not necessarily connected) such that every edge has length 1 and V≠∅. These properties guarantee that any connected component of any network is a geodesic metric space. Note that to exclude multiple edges and loops is not an important loss of generality, since [13, Theorems 8 and 10] reduce the problem of computing the hyperbolicity constant of graphs with multiple edges and/or loops to the study of simple graphs.IfX is a geodesic metric space and x1,x2,x3∈X, the union of three geodesics [x1x2], [x2x3], and [x3x1] is ageodesic triangle that will be denoted by T={x1,x2,x3} and we will say that x1,x2 and x3 are the vertices of T; it is usual to write also T=x1x2,[x2x3,[x3x1]}. We say that T is δ-thin if any side of T is contained in the δ-neighborhood of the union of the two other sides. We denote by δ(T) the sharp thin constant of T; that is, δ(T)≔inf{δ≥0:Tisδ-thin}. The space X is δ-hyperbolic(or satisfies theRips condition with constant δ) if every geodesic triangle in X is δ-thin. We denote by δ(X) the sharp hyperbolicity constant of X; that is, δ(X)≔sup{δ(T):TisageodesictriangleinX}. If we have a triangle with two identical vertices, we call it abigon; note that since this is a special case of the definition, every geodesic bigon in a δ-hyperbolic space is δ-thin. We say that X ishyperbolic if X is δ-hyperbolic for some δ≥0; then X is hyperbolic if and only if δ(X)<∞. If X has connected components {Xi}i∈I, then we define δ(X)≔supi∈Iδ(Xi), and we say that X is hyperbolic if δ(X)<∞.In the classical references on this subject (see, e.g., [1, 21]) several different definitions of Gromov hyperbolicity appear, which are equivalent in the sense that if X is δ-hyperbolic with respect to one definition, then it is δ′-hyperbolic with respect to another definition (for some δ′ related to δ). The definition that we have chosen has a deep geometric meaning (see, e.g., [1, 21]).Trivially, any bounded metric spaceX is (diam⁡X)-hyperbolic. A normed linear space is hyperbolic if and only if it has dimension one. A geodesic space is 0-hyperbolic if and only if it is a metric tree. If a complete Riemannian manifold is simply connected and its sectional curvatures satisfy K≤c for some negative constant c, then it is hyperbolic. See the classical reference [1, 21] in order to find further results.A network iscirculant if it has a cyclic group of automorphisms that includes an automorphism taking any vertex to any other vertex. There are large classes of circulant graphs. For instance, every cycle graph, complete graph, crown graph, and Möbius ladder is a circulant graph. A complete bipartite graph is a circulant graph if and only if it has the same number of vertices on both sides of its bipartition. A connected finite graph is circulant if and only if it is the Cayley graph of a cyclic group; see [22]. Every circulant graph is a vertex transitive graph and a Cayley graph [23].The circulant is a natural generalization of the double loop network and was first considered by Wong and Coppersmith [24]. Our main interest in circulant graphs lies in the role they play in the design of networks. In the area of computer networks, the standard topology is that of a ring network, that is, a cycle in graph theoretic terms. However, cycles have relatively large diameter, and in an attempt to reduce the diameter by adding edges, we wish to retain certain properties. In particular, we would like to retain maximum connectivity and vertex-transitivity. Hence, most of the earlier research concentrated on using the circulant graphs to build interconnection networks for distributed and parallel systems [25, 26]. The term circulant comes from the nature of its adjacency matrix. A matrix is circulant if all its rows are periodic rotations of the first one. Circulant matrices have been employed for designing binary codes [27]. Theoretical properties of circulant graphs have been studied extensively and surveyed [25].The study of the hyperbolicity constant in networks is usually a very difficult task; therefore, it is interesting to find bounds of this constant for particular classes of graphs. For a general graph or a general geodesic metric space deciding whether or not a space is hyperbolic is usually very difficult. Therefore, it is interesting to relate the hyperbolicity with other classes of graphs. The papers [10, 14, 15, 20] prove, respectively, that chordal, k-chordal, edge-chordal, and join graphs are hyperbolic. Moreover, in [10] it is shown that hyperbolic graphs are path-chordal graphs. The authors have proved in a previous work that every circulant graph is hyperbolic (and they obtain inequalities for the hyperbolicity constant of infinite circulant graphs). In this paper we obtain several sharp inequalities for the hyperbolicity constant of finite circulant networks; in some cases we characterize the graphs for which the equality is attained. Theorem 3 in Section 2 gives the precise value of the hyperbolicity constant of δ(Cn(a1)). Theorem 11 provides a sharp lower bound for δ(Cn(a1,a2,…,ak)) and characterizes the graphs for which the equality is attained. It is well known that a graph is circulant if and only if its complement is circulant. Thus it is natural to study in this context the properties of general complement graphs. In Theorems 15 and 24 this kind of results appears and they are applied to circulant graphs in Corollary 25. We collect in Section 3 several sharp inequalities for the hyperbolicity constant of a large class of circulant graphs. In Theorem 28 good lower and upper bounds for δ(Cn(1,a2,…,ak)) appear, which are improved in Theorems 29, 30, and 31 with additional hypothesis. Furthermore, we obtain the precise value of the hyperbolicity constant of many circulant networks (see Theorems 3, 11, and 29 and Corollary 25).


## 2. Bounds for the Hyperbolicity Constant

Given any natural numbern≥3, let {a1,a2,…,ak} be a set of integers such that 0<a1<⋯<ak≤⌊n/2⌋, where ⌊t⌋ denotes the lower integer part of t.We define the circulant networkCn(a1,…,ak) as the finite graph with vertices {1,2,…,n} (or {0,1,…,n-1}) such that N(j)={j±ai(mod⁡n)}i=1k is the set of neighbors of each vertex j. If ak≠n/2, then Cn(a1,…,ak) is a regular graph of degree 2k. For n even, we allow ak=n/2; in this case, Cn(a1,…,ak) is regular of degree 2k-1.The following result is well known (see, e.g., [28, Theorem 4.2]).Theorem 1.
The circulant graphCn(a1,…,ak) is connected if and only if gcd(a1,a2,…,ak,n)=1.If a circulant graphG has connected components G1,…,Gk, then Gi and Gj are isomorphic for every 1≤i,j≤k, Gj is also a circulant graph, and δ(G)=δ(Gj) for every 1≤j≤k. Thus the condition G connected is not a real restriction (unless if we deal with the complement graph of G, as in Theorems 15 and 24 and Corollary 25).As usual, bycycle we mean a simple closed curve, that is, a path with different vertices, unless the last one, which is equal to the first vertex.We also need the following result in [18, Theorem 11].Theorem 2.
IfCr is the cycle graph with r≥3 vertices, then δ(Cr)=r/4.The next result provides the precise value ofδ(Cn(a1)) for every value of n and a1.Theorem 3.
Ifn=ja1 with j≥2, then the circulant graph Cn(a1) has a1 connected components, δ(Cn(a1))=j/4 for every j≥3 and δ(Cn(a1))=0 if j=2.
Ifgcd(n,a1)=j<a1, then Cn(a1) has j connected components and δ(Cn(a1))=n/(4j).Proof.
Ifn=ja1, then it is clear that Cn(a1) has a1 connected components. If j=2, then Cn(a1) is the disjoint union of a1 edges and δ(Cn(a1))=0. If j≥3, then Cn(a1) is the disjoint union of a1 graphs isomorphic to Cj. Thus Theorem 2 gives δ(Cn(a1))=j/4.
Ifgcd(n,a1)=j<a1, then Cn(a1) is the disjoint union of j graphs isomorphic to Cn/j, and Theorem 2 gives δ(Cn(a1))=n/(4j).From [17, Proposition 5 and Theorem 7] we deduce the following result.Lemma 4.
LetG be any graph with a cycle g. If L(g)≥3, then δ(G)≥3/4. If L(g)≥4, then δ(G)≥1.For the sake of completeness, we are going to give an idea of the proof of this lemma. We need a definition and a lemma. We say that a subgraphΓ of G isisometric if dΓ(x,y)=dG(x,y) for every x,y∈Γ. It is easy to check that a subgraph Γ of G is isometric if and only if dΓ(u,v)=dG(u,v) for every u,v∈V(Γ). Isometric subgraphs are very important in the study of hyperbolic graphs, as the following result shows.Lemma 5 (see [18, Lemma 5]).
IfΓ is an isometric subgraph of G, then δ(Γ)≤δ(G).Let us start with the idea of the proof of Lemma4. If L(g)=3, then g is an isometric subgraph, and Lemma 5 and Theorem 2 give δ(G)≥δ(g)=δ(C3)=3/4. If L(g)=4, then the graph Γ induced by g is an isometric subgraph; thus, Γ is isomorphic to either C4, K4, or K4 without an edge, and Lemma 5 gives δ(G)≥δ(Γ)=1. Assume now that L(g)≥5 and there is no cycle in G of length 4. Let g0 be a curve with (2)Lg0=min⁡Lγ∣γisacycleinGwithLγ≥5. One can prove that g0 is an isometric subgraph and Lemma 5 and Theorem 2 give δ(G)≥δ(g0)=L(g0)/4≥5/4>1.Byx=±y we mean that we have either x=y or x=-y.Definition 6.
Givena0=0 and 1≤a1<a2<⋯<ak≤⌊n/2⌋ one says that the sequence {a1,a2,…,ak} is n-full if for every 0≤i≤n-1 and 1≤j≤k there exists 0≤k0≤k such that i=±ak0(mod⁡n) or i+aj=±ak0(mod⁡n).For any graphG, we define, as usual, (3)diam⁡VG≔sup⁡dGv,w∣v,w∈VG,diam⁡G≔sup⁡dGx,y∣x,y∈G.Definition 7.
One says that a vertexv of a graph G is acut-vertex if G∖{v} is not connected. A graph istwo-connected if it does not contain cut-vertices. Given any edge in G, let one consider the maximal two-connected subgraph containing it. One calls to the set of these maximal two-connected subgraphs {Gs} thecanonical T-decomposition of G. One defines the effective diameter of G as (4)effdiam⁡VG≔supsdiam⁡VGs,effdiam⁡G≔supsdiam⁡Gs.Note that ifG is a two-connected graph, then effdiam⁡V(G)=diam⁡V(G) and effdiam⁡G=diam⁡G.We need the following result in [12, Proposition 4.5 and Theorem 4.14].Theorem 8.
A graphG verifies δ(G)=1 if and only if effdiam⁡G=2. Furthermore, δ(G)≤1 if and only if effdiam⁡G≤2.We need the following result in [18, Theorem 8].Theorem 9.
In any graphG the inequality δ(G)≤(diam⁡G)/2 holds.We have the following direct consequence.Corollary 10.
In any graphG the inequality δ(G)≤(diam⁡V(G)+1)/2 holds.Denote byJ(G) the set of vertices and midpoints of edges in G.Since Theorem3 gives the precise value of δ(Cn(a1)), in order to study δ(Cn(a1,a2,…,ak)) we just need to deal with the case k>1.We prove now a sharp lower bound for the hyperbolicity constant and we characterize the graphs for which this lower bound is attained.Theorem 11.
For any integersk>1 and 1≤a1<a2<⋯<ak≤⌊n/2⌋ such that Cn(a1,a2,…,ak) is connected, one has (5)δCna1,a2,…,ak≥1,and δ(Cn(a1,a2,…,ak))=1 if and only if {a1,a2,…,ak} is n-full.Proof.
We are going to prove thatCn(a1,a2,…,ak) contains a cycle with length at least 4.
Assume first thatlcm(aj,n)/aj≥4 for some 1≤j≤k. Thus, Cn(a1,a2,…,ak) contains a cycle with length at least 4.
Assume now thatlcm(aj,n)/aj≤3 for every 1≤j≤k. Seeking for a contradiction assume that lcm(aj,n)/aj=1 for some 1≤j≤k. Then lcm(aj,n)=aj and n≤aj, contradicting aj≤⌊n/2⌋. So, 2≤lcm(aj,n)/aj≤3 for every 1≤j≤k. If lcm(aj,n)/aj=2 for some 1≤j≤k, then aj=n/2=ak. If lcm(aj,n)/aj=3 for some 1≤j≤k, then aj=n/3. Since k>1, we deduce k=2, a1=n/3, and a2=n/2, and there exists a positive integer n0 such that n=6n0, a1=2n0, and a2=3n0. Since Cn(a1,a2,…,ak) is connected, Theorem 1 gives that 1=gcd(a1,a2,n)=gcd(2n0,3n0,6n0)=n0. Hence, C6n0(2n0,3n0)=C6(2,3), and the cycle with consecutive vertices {0,2,4,1,5,3,0} has length 6≥4.
Thus,Cn(a1,a2,…,ak) contains a cycle with length at least 4 in any case, and Lemma 4 gives δ(Cn(a1,a2,…,ak))≥1.
Denote by{0,1,…,n-1} the vertices of G≔Cn(a1,a2,…,ak).
Assume first that{a1,a2,…,ak} is n-full. We are going to show that d(x,y)≤3/2 for every x∈V(G) and y∈J(G)∖V(G). Since G is a circulant graph, we can assume x=0 by symmetry. Since y∈J(G)∖V(G), there exist 0≤i≤n-1 and 1≤j≤k such that y belongs to [i,i+aj]. Thus there exists 0≤k0≤k such that i=±ak0(mod⁡n) or i+aj=±ak0(mod⁡n), and we have d(0,[i,i+aj])≤1. Hence, d(0,y)=d(0,[i,i+aj])+1/2≤1+1/2=3/2. Therefore, d(x,y)≤3/2 for every x∈V(G) and y∈J(G)∖V(G), and we conclude d(x,y)≤2 for every x,y∈V(G) and for every x,y∈J(G)∖V(G). Thus diam⁡G≤2 and Theorem 9 gives δ(G)≤1, and we conclude δ(G)=1.
Assume now thatδ(G)=1. Since G is a two-connected graph, Theorem 8 gives diam⁡G=2. Hence, d(x,y)≤3/2 for every x∈V(G) and y∈J(G)∖V(G). Consider 0≤i≤n-1 and 1≤j≤k and let y be the midpoint of [i,i+aj]. Therefore, d(0,y)≤3/2 implies d(0,[i,i+aj])≤1. Thus there exists 0≤k0≤k such that i=±ak0(mod⁡n) or i+aj=±ak0(mod⁡n), and we conclude that {a1,a2,…,ak} is n-full.In [11, Theorem 2.6] the following result appears.Theorem 12.
For every hyperbolic graphG, δ(G) is a multiple of 1/4.Theorems11 and 12 have the following consequences.Corollary 13.
For any integersk>1 and 1≤a1<a2<⋯<ak≤⌊n/2⌋ such that Cn(a1,a2,…,ak) is connected, one has (6)δCna1,a2,…,ak≥54if and only if {a1,a2,…,ak} is not n-full.Corollary 14.
For any integers4≤n≤6, k>1, and 1<a2<⋯<ak≤⌊n/2⌋, one has (7)δCn1,a2,…,ak=1,and δ(C6(2,3))=5/4.Proof.
If we have eithern=4 or n=5, then k=2=⌊n/2⌋ and {a1,a2}={1,2}, and so diam⁡V(Cn(1,2))=1 and Corollary 10 gives δ(Cn(1,2))≤1. Theorem 11 gives the converse inequality.
Assume thatn=6. If k=3=⌊n/2⌋, then {a1,a2,a3}={1,2,3}, and the previous argument gives δ(C6(1,2,3))=1. If k=2, then we have either a2=2 or a2=3. If a2=2, then we have 0=a0, 1=a1, 2=a2, 4=-2(mod⁡6)=-a2(mod⁡6), 5=-1(mod⁡6)=-a1(mod⁡6), 3+1=4=-2(mod⁡6)=-a2(mod⁡6), and 3+2=5=-1(mod⁡6)=-a1(mod⁡6), and Theorem 11 gives δ(C6(1,2))=1. If a2=3, then we have 0=a0, 1=a1, 3=a2, 5=-1(mod⁡6)=-a1(mod⁡6), 2+1=3=a2, 2+3=5=-1(mod⁡6)=-a1(mod⁡6), 4+1=5=-1(mod⁡6)=-a1(mod⁡6), and 4+3=7=1(mod⁡6), and Theorem 11 gives δ(C6(1,3))=1.
Finally, considerC6(2,3), i=5, j=1, and i+aj=5+2=1(mod⁡6). Since 1≠±2(mod⁡6), 1≠±3(mod⁡6), 5≠±2(mod⁡6), and 5≠±2(mod⁡6), Corollary 13 gives δ(C6(2,3))≥5/4. One can check that diam⁡C6(2,3)=5/2, and Theorem 9 gives δ(C6(2,3))≤5/4.It is well known that a graph is circulant if and only if its complement is circulant. Thus it is natural to study in this context the properties of general complement graphs. In Theorems15 and 24 this kind of results appears and they are applied to circulant graphs in Corollary 25.As usual, thecomplementG¯ of the (connected or nonconnected) graph G is defined as the graph with V(G¯)=V(G) such that e∈E(G¯) if and only if e∉E(G).Theorem 15.
IfG is a graph with diam⁡V(G)≥4, then G¯ is connected and δ(G¯)≤3/2, and this inequality is sharp.Proof.
Seeking for a contradiction assume that there exists an edgee∈E(G) such that dG(e,v)≤1 for every v∈V(G). Choose u,v∈V(G) with dG(u,v)=4. Thus 4=dG(u,v)≤dG(u,e)+L(e)+dG(e,v)≤3, which is a contradiction. Hence, for each edge e∈E(G) there exists v∈V(G) with dG(e,v)≥2.
Fixw1,w2∈V(G). If dG(w1,w2)>1, then [w1,w2]∉E(G), [w1,w2]∈E(G¯), and dG¯(w1,w2)=1. If dG(w1,w2)=1, then there exists v∈V(G) with dG([w1,w2],v)≥2. Thus w1,v,[w2,v]∉E(G), w1,v,[w2,v]∈E(G¯), and dG¯(w1,w2)≤dG¯(w1,v)+dG¯(v,w2)=2. Hence, G¯ is connected, diam⁡V(G¯)≤2, and Corollary 10 gives the inequality.
The following family of graphs shows that this inequality is sharp. Letn≥912 be an even integer and G=Cn(2,6,8,n/2-2,n/2-1). Since G is a 10-regular graph and n≥912>911=1+10(1+9+92), the Moore’s bound gives diam⁡V(G)≥4. Hence, we have proved that δ(G¯)≤3/2 and it suffices to show that δ(G¯)≥3/2. Denote by {0,1,…,n-1} the vertices of G and consider the cycle C in G¯ with length 6 and consecutive vertices {1,2,n-1,n-4,n/2,4,1}. Let x, y be the midpoints of [1,4] and [n-4,n-1], respectively, and γ1, γ2 the two geodesics contained in C joining x and y with vertices {4,n/2,n-4} and {1,2,n-1}, respectively. Since [n/2,1],[n/2,2],[n/2,n-1]∈E(G), we have [n/2,1],[n/2,2],[n/2,n-1]∉E(G¯) and (8)δG¯≥dG¯n2,γ2=dG¯n2,x,y=32.Theorem24 below gives more information than Theorem 15 for nonconnected graphs. In order to prove it, we need some technical results.Lemma 16.
IfG is a nonconnected graph with connected components G1,…,Gk and dGj¯(v,e)≤1 for every v∈V(Gj¯), e∈E(Gj¯), and 1≤j≤k, then diam⁡G¯≤2.Proof.
Note that it suffices to check thatdG¯(x,v)≤3/2 for every x∈J(G¯)∖V(G¯) and v∈V(G¯).
Letx be the midpoint of [v′,v′′]∈E(Gj¯) for some 1≤j≤k. If v∈V(Gj¯), then dG¯(x,v)≤3/2 since diam⁡Gj¯≤2. If v∈V(Gi¯) for some i≠j, then dG¯(x,v)≤dG¯(x,v′)+dG¯(v′,v)=3/2.
Letx be the midpoint of [vi,vj]∈E(G¯) with vi∈V(Gi¯), vj∈V(Gj¯), and i≠j. If v∈V(Gi¯), then dG¯(x,v)≤dG¯(x,vj)+dG¯(vj,v)=3/2. If v∉V(Gi¯), then dG¯(x,v)≤dG¯(x,vi)+dG¯(vi,v)=3/2.
Hence,dG¯(x,v)≤3/2 for every x∈J(G¯)∖V(G¯) and v∈V(G¯), and we conclude diam⁡G¯≤2.Note that a connected graphΓ satisfies dΓ(v,e)≤1 for every v∈V(Γ), e∈E(Γ) if and only if diam⁡Γ≤2. A nonconnected graph Γ satisfies this property if and only if E(Γ)=∅.We have the following direct consequence of Lemma16.Corollary 17.
IfG is a nonconnected graph with connected components G1,…,Gk and diam⁡Gj¯≤2 for every 1≤j≤k, then diam⁡G¯≤2.LetG=(V(G),E(G)) and Γ=(V(Γ),E(Γ)) be two graphs with V(G)∩V(Γ)=∅. We recall that thegraph joinG⊎Γ of G and Γ is the graph such that V(G⊎Γ)=V(G)∪V(Γ) and two different vertices u and v of G⊎Γ are adjacent if u∈V(G) and v∈V(Γ), or [u,v]∈E(G) or [u,v]∈E(Γ).The argument in the proof of Lemma16 gives the following result.Corollary 18.
IfG and Γ are graphs with diam⁡G≤2 and diam⁡Γ≤2, then diam⁡(G⊎Γ)≤2.Definition 19.
One says that a nonconnected graphG with connected components G1,…,Gk satisfies the 1-vertex-edge property if we have either dGj¯(v,e)≤1, for every v∈V(Gj¯), e∈E(Gj¯), and 1≤j≤k, or k=2, |V(G1)|=1, and diam⁡Γi≤2, for every 1≤i≤r, where Γ1,…,Γr(r≥1) are the connected components of G2¯, or k=2, |V(G2)|=1, and diam⁡Γi≤2 for every 1≤i≤r where Γ1,…,Γr(r≥1) are the connected components of G1¯.Theorem 20.
LetG be a nonconnected graph with connected components G1,…,Gk. Then effdiam⁡G¯≤2 if and only if G satisfies the 1-vertex-edge property.Proof.
Assume thatdGj¯(v,e)≤1 for every v∈V(Gj¯), e∈E(Gj¯), and 1≤j≤k. Lemma 16 gives effdiam⁡G¯≤diam⁡G¯≤2.
Assume now thatk=2, |V(G1)|=1, and diam⁡Γi≤2 for every 1≤i≤r where Γ1,…,Γr(r≥1) are the connected components of G2¯. If V(G1)={v}, then we define for each 1≤i≤r the graph Γi′={v}⊎Γi. Corollary 18 gives that diam⁡Γi′≤2. Since {Γi′} is the canonical T-decomposition of G¯, we conclude that effdiam⁡G¯=max1≤i≤rdiam⁡Γi′≤2.
Ifk=2, |V(G2)|=1, and diam⁡Γi≤2 for every 1≤i≤r where Γ1,…,Γr(r≥1) are the connected components of G1¯, then the previous argument also gives effdiam⁡G¯≤2.
Finally, assume thateffdiam⁡G¯≤2.
Note thatG¯ has a cut-vertex if and only if k=2 and we have either |V(G1)|=1 and G2¯ being nonconnected or |V(G2)|=1 and G1¯ being nonconnected.
Assume thatG¯ has a cut-vertex. By symmetry we can assume that k=2, |V(G1)|=1, and G2¯ is nonconnected. Let Γ1,…,Γr(r≥2) be the connected components of G2¯, and consider Γ1′,…,Γr′ defined as before. Thus diam⁡Γi′≤effdiam⁡G¯≤2 for every 1≤i≤r. Seeking for a contradiction assume that diam⁡Γi>2 for some 1≤i≤r. Then dΓi(x,v)=5/2 for some x∈J(Γi)∖V(Γi′) and v∈V(Γi), and we conclude dΓi′(x,v)=5/2, which is a contradiction. Hence, diam⁡Γi≤2 for every 1≤i≤r, and G satisfies the 1-vertex-edge property.
Assume now thatG¯ does not have cut-vertices. Thus diam⁡G¯=effdiam⁡G¯≤2. Seeking for a contradiction assume that dGj¯(v,e)≥2 for some v∈V(Gj¯), e∈E(Gj¯), and 1≤j≤k. If x is the midpoint of e, then dGj¯(x,v)≥5/2, and we conclude dG¯(x,v)=5/2, which is a contradiction. Hence, dGj¯(v,e)≤1 for every v∈V(Gj¯), e∈E(Gj¯), and 1≤j≤k, and G satisfies the 1-vertex-edge property.Consider the setT1 of geodesic triangles T in G that are cycles such that the three vertices of the triangle T belong to J(G).The following result appears in [11, Theorem 2.7].Theorem 21.
For any hyperbolic graphG there exists a geodesic triangle T∈T1 such that δ(T)=δ(G).The following result in [17, Theorem 11] will be useful.Theorem 22.
IfG is a graph with δ(G)<1, then one has either δ(G)=0 or δ(G)=3/4. Furthermore,(i)
δ(G)=0 if and only if G is a tree;(ii)
δ(G)=3/4 if and only if δ(G)>0 and every cycle g in G has length L(g)=3.Definition 23.
Given a graphG with diam⁡V(G)=2, one says that a subgraph G0 contains amaximal triangle and there exists a geodesic triangle T in G that is a cycle such that x,y,z∈J(G), δ(T)=3/2, and T is contained in G0.Note that ifG0 contains a maximal triangle T, then we can rename the vertices of T in order to guarantee that there exists p∈[xy] such that dG(p,[xz]∪[zy])=dG(p,x)=dG(p,y)=L([xy])/2=δ(T)=3/2, x,y∈J(G)∖V(G), and p∈V(G). Furthermore, L([yz])≤3 and L([xz])≤3.The following result provides the precise value ofδ(G¯) for every nonconnected graph G.Theorem 24.
IfG is a nonconnected graph with connected components G1,…,Gk, then G¯ is connected and δ(G¯)≤3/2. Furthermore,(i)
δ(G¯)=0 if and only if k=2 and G1 and G2 are complete graphs and we have |V(G1)|=1 or |V(G2)|=1;(ii)
δ(G¯)=3/4 if and only if δ(G¯)>0 and we have either k=3, |V(G1)|=|V(G2)|=|V(G3)|=1, or k=2, |V(G1)|=1, and G2 being isomorphic to a complete graph without a nonempty set of pairwise disjoint edges, or k=2, |V(G2)|=1, and G1 being isomorphic to a complete graph without a nonempty set of pairwise disjoint edges;(iii)
δ(G¯)=1 if and only if δ(G¯)>3/4 and G satisfies the 1-vertex-edge property;(iv)
δ(G¯)=5/4 if and only if δ(G¯)>1 and Gj¯ does not contain a maximal triangle for every 1≤j≤k;(v)
δ(G¯)=3/2 if and only if Gj¯ contains a maximal triangle for some 1≤j≤k.Proof.
Theorem15 gives that G¯ is connected and δ(G¯)≤3/2. Furthermore, the argument in the proof of Theorem 15 provides that diam⁡V(G¯)≤2 and thus diam⁡G¯≤3.
G
¯ is a tree if and only if k=2 and G1 and G2 are complete graphs and we have |V(G1)|=1 or |V(G2)|=1. This gives the first item.
G
¯ is not a tree and every cycle g in G¯ has length L(g)=3 if and only if we have either k=3, |V(G1)|=|V(G2)|=|V(G3)|=1 (if G¯ does not have cut-vertices), or k=2, |V(G1)|=1, and G2 being isomorphic to a complete graph without a nonempty set of pairwise disjoint edges, or k=2, |V(G2)|=1, and G1 being isomorphic to a complete graph without a nonempty set of pairwise disjoint edges (if G¯ has a cut-vertex). Thus Theorem 22 gives the second item.
Assume thatδ(G¯)=3/2. By Theorem 9, we have diam⁡G¯=3 and diam⁡V(G¯)=2. By Theorem 21, there exist a geodesic triangle T={x,y,z} that is a cycle in G¯ and p∈[xy] such that dG¯(p,[xz]∪[zy])=δ(T)=δ(G¯)=3/2 and x,y,z∈J(G¯). Since diam⁡G¯=3 and diam⁡V(G¯)=2, we have L([xy])/2=dG¯(p,x)=dG¯(p,y)=dG¯(p,[xz]∪[zy])=δ(T)=δ(G¯)=3/2 and p is the midpoint of [xy]. Thus x,y∈J(G¯)∖V(G¯) and p∈V(G¯). Besides, L([yz])≤3 and L([xz])≤3.
Letq be the midpoint of [vi,vj]∈E(G¯) with vi∈V(Gi¯), vj∈V(Gj¯), and i≠j. If v∈V(Gi¯), then dG¯(q,v)≤dG¯(q,vj)+dG¯(vj,v)=3/2. If v∉V(Gi¯), then dG¯(q,v)≤dG¯(q,vi)+dG¯(vi,v)=3/2. Hence, dG¯(q,v)≤3/2 for every v∈V(G¯) and dG¯(q,w)≤2 for every w∈J(G¯).
Letq be the midpoint of [v′,v′′]∈E(Gj¯) for some 1≤j≤k and v∈V(Gi¯) for some i≠j. Thus, dG¯(q,v)=3/2 and dG¯(q,w)≤2 for every w∈J(G¯)∖J(Gj¯).
Therefore, there exist1≤j≤k and v′,v′′,[w′,w′′]∈E(Gj¯) such that x and y are the midpoints of [v′,v′′] and [w′,w′′], respectively. By symmetry, we can assume that v′,w′∈[xy], and so V(G¯)∩[xy]={v′,p,w′}. Since T is a cycle, v′′,w′′∈[xz]∪[zy]. If p∉V(Gj¯), then 3/2=dG¯(p,[xz]∪[zy])≤dG¯(p,v′′)=1, which is a contradiction. Hence, p∈V(Gj¯). If there exists a vertex v∈V(G¯)∩([xz]∪[zy]) with v∉V(Gj¯), then 3/2=dG¯(p,[xz]∪[zy])≤dG¯(p,v)=1, which is a contradiction. Therefore, T∩V(G¯)⊆Gj¯ and so T is a maximal triangle in Gj¯.
Assume now thatGj¯ contains a maximal triangle T for some 1≤j≤k. Thus 3/2=δ(T)≤δ(G¯) and, since δ(G¯)≤3/2, we conclude δ(G¯)=3/2.
Theorem20 gives that effdiam⁡G¯≤2 if and only if G satisfies the 1-vertex-edge property. By Theorem 8, δ(G¯)≤1 if and only if G satisfies the 1-vertex-edge property. Theorem 12 gives δ(G¯)>3/4 if and only if δ(G¯)≥1. Hence, δ(G¯)=1 if and only if δ(G¯)>3/4 and G satisfies the 1-vertex-edge property.
Finally, the previous results and Theorem12 provide the characterization of the graphs G with δ(G¯)=5/4.Theorem24 has the following consequence for circulant graphs.Corollary 25.
Fix integersk≥1 and 1≤a1<a2<⋯<ak≤⌊n/2⌋ such that G≔Cn(a1,a2,…,ak) is nonconnected, and consider integers r>1 and 1≤b1<b2<⋯<bk≤⌊n/(2r)⌋ such that Cn(a1,a2,…,ak) has r connected components isomorphic to Cn/r(b1,b2,…,bk). Then G¯ is a connected circulant graph and 1≤δ(G¯)≤3/2. Furthermore,(i)
δ(G¯)=1 if and only if we have either diam⁡Cn/r(b1,b2,…,bk)¯≤2 or Cn/r(b1,b2,…,bk) being a complete graph;(ii)
δ(G¯)=5/4 if and only if δ(G¯)>1 and Cn/r(b1,b2,…,bk)¯ does not contain a maximal triangle;(iii)
δ(G¯)=3/2 if and only if Cn/r(b1,b2,…,bk)¯ contains a maximal triangle.Proof.
Since1≤⌊n/(2r)⌋ and |V(Cn/r(b1,b2,…,bk))|=n/r≥2>1. Hence, G satisfies the 1-vertex-edge property if and only if we have either diam⁡Cn/r(b1,b2,…,bk)¯≤2 or Cn/r(b1,b2,…,bk) being the complete graph with n/r vertices. Thus Theorem 24 gives the result.


## 3. Bounds for the Hyperbolicity Constant Ifa1=1

The following result is well known (see, e.g., [28, Proposition 5.1]).Theorem 26.
IfCn(a1,a2,…,ak) is such that gcd(n,ai)=1 for some i with 1≤i≤k, then there exists a circulant graph Cn(b1,b2,…,bk) isomorphic to Cn(a1,a2,…,ak) with b1=1.Hence, it is natural to find bounds for the hyperbolicity constant ofCn(1,a2,…,ak). We will need the following result.IfH is a subgraph of G and w∈V(H), we denote by degH(w) the degree of the vertex w in the subgraph induced by V(H).Theorem 27 (see [12, Theorem 3.2]).
LetG be any graph. Then δ(G)≥5/4 if and only if there exist a cycle g in G with length L(g)≥5 and a vertex w∈g such that degg(w)=2.The following result provides good lower and upper bounds ifa1=1.Theorem 28.
For any integersk>1 and 1<a2<⋯<ak≤⌊n/2⌋ one has(9)12n2ak≤δCn1,a2,…,ak≤12n2ak+ak+14,if n-2ak⌊n/(2ak)⌋∈{ak+1,ak+2,2ak-1}, and(10)12n2ak≤δCn1,a2,…,ak≤12n2ak+ak4,otherwise. The second equality in (9) is attained if k=2, a2 is odd, and n-2a2⌊n/(2a2)⌋=a2+1. The second equality in (10) is attained if k=2 and n is an odd multiple of a2.Proof.
Let us denote by{0,1,…,n-1} the vertices of G≔Cn(1,a2,…,ak), and let us denote by Cn the subgraph of G with V(Cn)=V(G) and E(Cn)={[0,1],[1,2],…,[n-2,n-1],[n-1,1]}.
We prove first the upper bounds.
We are going to find an upper bound ofdiam⁡G. We want to remark that it is not possible to find a simple formula for diam⁡G (and not even for diam⁡V(G), see [28]).
Fix a vertexv∈V(G), and denote by v′,v′′ the vertices with dCn(v,v′)=dCn(v,v′′)=ak⌊n/(2ak)⌋ (if n is a multiple of 2ak, then v′=v′′); therefore, dCn(v′,v′′)=n-2ak⌊n/(2ak)⌋ and dG(v,v′)=dG(v,v′′)=⌊n/(2ak)⌋. For each real number t with 0≤t≤dCn(v′,v′′)≤2ak-1, define vt as the point in Cn with dCn(vt,v′)=t and dCn(vt,v)≥ak⌊n/(2ak)⌋.
Assume that0<dCn(v′,v′′)≤ak-1 (the case dCn(v′,v′′)=0 is trivial).
We have(11)dGv,vt≤n2ak+min⁡t,dCnv′,v′′-t≤n2ak+min⁡t,ak-1-t≤n2ak+ak-12.
IfdCn(v′,v′′)>ak, then we define v′′′ as the vertex verifying dCn(v′′′,v′′)=ak and dCn(v′′′,v′)=dCn(v′,v′′)-ak. Assume that ak+3≤dCn(v′,v′′)≤2ak-2. Then 3≤dCn(v′′′,v′)≤ak-2 and we have dCn(v′′′,v′)-1≤ak-3 and ak-dCn(v′′′,v′)≤ak-3; hence, for 0≤t≤ak, (12)dGv,vt≤n2ak+1+12max⁡dCnv′′′,v′-1,ak-dCnv′′′,v′≤n2ak+ak-12.Using a symmetric argument we obtain the same inequality for ak<t≤dCn(v′,v′′).
Hence, one can check that(13)dGv,p≤n2ak+ak-12holds for every p∈G, if 0≤dCn(v′,v′′)≤ak-1 or ak+3≤dCn(v′,v′′)≤2ak-2. Since G is equal to the closed ball or radius ⌊n/(2ak)⌋+(ak-1)/2 and center v for every v∈V(G), we conclude diam⁡G≤⌊n/(2ak)⌋+ak/2 in this case.
Assume now thatdCn(v′,v′′)∈{ak+2,2ak-1}. Then dCn(v′′′,v′)∈{2,ak-1} and we have dCn(v′′′,v′)-1≤ak-2 and ak-dCn(v′′′,v′)≤ak-2; hence, for 0≤t≤ak, (14)dGv,vt≤n2ak+1+12max⁡dCnv′′′,v′-1,ak-dCnv′′′,v′≤n2ak+ak2.Using a symmetric argument we obtain the same inequality for ak<t≤dCn(v′,v′′). Hence, (15)dGv,p≤n2ak+ak2holds for every p∈G, and we conclude diam⁡G≤⌊n/(2ak)⌋+(ak+1)/2 in this case.
IfdCn(v′,v′′)=ak (n is an odd multiple of ak), then a similar argument gives dG(v,p)≤⌊n/(2ak)⌋+ak/2 for every p∈G. If z is the midpoint of [u,v]∈E(G), then the previous argument gives (16)Bz,n2ak+ak2¯=Bu,n2ak+ak-12¯∪Bv,n2ak+ak-12¯=G.Hence, we also obtain diam⁡G≤⌊n/(2ak)⌋+ak/2 in this case.
IfdCn(v′,v′′)=ak+1, then a similar argument gives dG(v,p)≤⌊n/(2ak)⌋+(ak+1)/2 for every p∈G. If z is the midpoint of [u,v]∈E(G), then the previous argument gives (17)Bz,n2ak+ak+12¯=Bu,n2ak+ak2¯∪Bv,n2ak+ak2¯=G.Thus, we obtain diam⁡G≤⌊n/(2ak)⌋+(ak+1)/2 in this case.
Therefore, Theorem9 gives the desired inequalities.
Assume now thatk=2 and n is an odd multiple of a2. Define t≔⌊a2/2⌋ and s≔⌊n/(2a2)⌋. Fix a vertex v∈V(G), and denote by v1,…,vt,v1′,…,vt′,z1,…,zs,z1′,…,zs′ vertices with dCn(v,vj)=j for 1≤j≤t,  dCn(vj,vj+1)=1 for 1≤j<t,  dCn(zj,v)=t+ja2=t+dCn(zj,vt) for 1≤j≤s,  dCn(zj′,v)=ja2 for 1≤j≤s,  dCn(zj′,zj+1′)=a2 for 1≤j<s,  dCn(vj′,v)=sa2+j=sa2+dCn(vj′,zs′) for 1≤j≤t, and dCn(z1′,v1)=1+a2. Define (18)γ0≔v,v1∪v1,v2∪⋯∪vt-1,vt∪vt,z1∪z1,z2∪⋯∪zs-1,zs,γ0′≔v,z1′∪z1′,z2′∪⋯∪zs-1′,zs′∪zs′,v1′∪v1′,v2′∪⋯∪vt-1′,vt′.Since n is an odd multiple of a2, we have (19)dCnv,zs=dCnv,vt′=t+sa2=n2a2a2+a22=n2+a22-a22.Hence, zs=vt′ if a2 is even and dCn(zs,vt′)=1 if a2 is odd; let w be the midpoint of [zsvt′] and define γ≔γ0∪[zsw] and γ′≔γ0′∪[vt′w]. Then γ and γ′ are geodesics and L(γ)=L(γ′)=dG(v,w)=⌊n/(2a2)⌋+a2/2. Let T be the geodesic bigon T={γ,γ′} and p the midpoint of γ. We have (20)δG≥dGp,γ′=dGp,v,w=12dGv,w=12n2a2+a24.Since we have proved the converse inequality, we conclude that the equality holds.
Assume thatk=2, a2 is odd and n-2a2⌊n/(2a2)⌋=a2+1. We obtain the equality by using a similar bigon to the previous case, with t≔(a2+1)/2.
Finally, we prove the lower bound. By Theorem11, we can assume that ⌊n/(2ak)⌋≥2.
Let us definex=0, y=ak⌊n/(2ak)⌋, and z=n-ak⌊n/(2ak)⌋ (if n is a multiple of 2ak, then y=z). Consider the geodesics (21)xy≔0,ak∪ak,2ak∪⋯∪n2ak-1ak,n2akak,xz≔0,n-ak∪n-ak,n-2ak∪⋯∪n-n2ak-1ak,n-n2akak.We define an appropriate geodesic [yz] in the following way. A geodesic g can be obtained as(22)g≔y,y+aj1∪y+aj1,y+aj2∪⋯∪y+∑i=1r-1aji,y+∑i=1raji∪y+∑i=1raji,y+∑i=1raji-aj1′∪y+∑i=1raji-aj1′,y+∑i=1raji-aj1′-aj2′∪⋯∪y+∑i=1raji-∑i=1r′-1aji′,y+∑i=1raji-∑i=1r′aji′,with r≥r′≥0 and r+r′=dG(y,z) (if r′=0, then the part of g with negative numbers does not appear).
Let us define the finite sequence{t1,…,tr} in the following way: (23)ts≔max⁡m∈N∣∑i=1saji-∑i=1maji′≥0if ∑i=1saji-aj1′≥0, and ts≔0 otherwise (i.e., we define ∑i=10aji′=0). It is clear that t1≤⋯≤tr and tr=r′.
Consider1<s≤r. If ts-1=0, then (24)∑i=1s-1aji<aj1′,∑i=1saji-∑i=1ts-1aji′=∑i=1s-1aji+ajs<aj1′+ajs≤2ak.If ts-1=r′, then (25)∑i=1saji-∑i=1ts-1aji′=∑i=1saji-∑i=1r′aji′≤∑i=1raji-∑i=1r′aji′=z-y<2ak.If 0<ts-1<r′, then (26)∑i=1s-1aji-∑i=1ts-1aji′<ajts-1+1′≤ak,and so, (27)∑i=1saji-∑i=1ts-1aji′=ajs+∑i=1s-1aji-∑i=1ts-1aji′<ajs+ak≤2ak.
Let us define(28)γ1≔y,y+aj1∪y+aj1,y+aj1-aj1′∪y+aj1-aj1′,y+aj1-aj1′-aj2′∪⋯∪y+aj1-∑i=1t1-1aji′,y+aj1-∑i=1t1aji′,γs≔y+∑i=1s-1aji-∑i=1ts-1aji′,y+∑i=1saji-∑i=1ts-1aji′∪y+∑i=1saji-∑i=1ts-1aji′,y+∑i=1saji-∑i=1ts-1+1aji′∪⋯∪y+∑i=1saji-∑i=1ts-1aji′,y+∑i=1saji-∑i=1tsaji′,for 1<s≤r (if ts=ts-1, then γs is a single edge). We have (29)Lγ1=1+t1,Lγs=1+ts-ts-1,1<s≤r,Lγ1∪⋯∪γr=r+tr=r+r′=dGy,z.Since γ1∪⋯∪γr joins y and z, and L(γ1∪⋯∪γr)=dG(y,z), we consider the geodesic [yz]≔γ1∪⋯∪γr.
Since(30)∑i=1saji-∑i=1tsaji′≥0,we have v≥y for every v∈[yz]∩V(G).
Since⌊n/(2ak)⌋≥2, we have (31)∑i=1saji-∑i=1ts-1aji′≤2ak≤n-z≤n-y, and we conclude that y≤v≤n for every v∈[yz]∩V(G). Let p be the midpoint of [xy]. Since y≤v≤n for every v∈([yz]∩[xz])∩V(G), (32)δG≥dGp,yz∪xz=dGp,x,y=12Lxy=12n2ak.The lower bound in Theorem28 can be improved for k=2.Theorem 29.
For any integers1<a2≤⌊n/2⌋ with n-2a2⌊n/(2a2)⌋≤a2+1 one has(33)δCn1,a2≥12n2a2+14n-2a2n2a2.The equality in (33) is attained if n-2a2⌊n/(2a2)⌋=a2+1.Proof.
Let us denote by{0,1,…,n-1} the vertices of G≔Cn(1,a2,…,ak), and let us denote by Cn the subgraph of G with V(Cn)=V(G) and E(Cn)={[0,1],[1,2],…,[n-2,n-1],[n-1,1]}.
Letv=0, v′=a2⌊n/(2a2)⌋, and v′′=n-a2⌊n/(2a2)⌋. Thus dCn(v,v′)=dCn(v,v′′)=a2⌊n/(2a2)⌋ (if n is a multiple of 2a2, then v′=v′′); therefore, dCn(v′,v′′)=n-2a2⌊n/(2a2)⌋ and dG(v,v′)=dG(v,v′′)=⌊n/(2a2)⌋. Note 0≤dCn(v′,v′′)=n-2a2⌊n/(2a2)⌋≤a2+1.
IfdCn(v′,v′′)=0, then Theorem 28 gives (33).
Assume that0<dCn(v′,v′′)≤a2+1. Define v0 as the point in Cn with dCn(v0,v′)=dCn(v0,v′)=dCn(v′,v′′)/2. One can check that dG(v0,v′)=dCn(v0,v′)=dCn(v′,v′′)/2. Define g1≔[vv′] as the geodesic in G with g1∩V(G)={0,a2,2a2,…,a2⌊n/(2a2)⌋} and g2≔[vv′′] the geodesic in G with g2∩V(G)={0,n-a2,n-2a2,…,n-a2⌊n/(2a2)⌋}. Let g1′≔[v′v0] and g2′≔[v′′v0] be geodesics in G contained in Cn. Thus γ1≔g1∪g1′ and γ2≔g2∪g2′ are two geodesics in G joining v and v0. If p is the midpoint of γ1, then (34)δG≥dGp,γ2=dGp,v,v0=12Lγ1=12n2a2+14dCnv′,v′′=12n2a2+14n-2a2n2a2.
Theorem28 gives that the equality in (33) is attained if n-2a2⌊n/(2a2)⌋=a2+1.The upper bounds in Theorem28 can be improved for k large enough.Theorem 30.
Consider any integersk>1 and 1<a2<⋯<ak≤⌊n/2⌋. Assume that k≥(n-1)/4 if ak≠n/2 and k≥(n+1)/4 if ak=n/2. Then one has (35)1≤δCn1,a2,…,ak≤32.Proof.
By Theorem11, it suffices to prove the upper bound. Recall that if ak≠n/2, then G≔Cn(1,a2,…,ak) is a regular graph with degree Δ=2k and that if ak=n/2, then G is regular with degree Δ=2k-1. In any case we have deg(v1)+deg(v2)=2Δ≥n-1 for every v1,v2∈V(G). Therefore, given any u,v∈V(G) with dG(u,v)>1, there exists a vertex w with dG(u,w)=dG(v,w)=1; thus dG(u,v)=2 and we conclude that diam⁡V(G)=2. Then Corollary 10 gives δ(G)≤3/2.Note that by Theorem12, under the hypothesis in Theorem 30, the possible values for δ(Cn(1,a2,…,ak)) are just 1, 5/4, and 3/2.Finally, the next result estimates the hyperbolicity constant ifak=k.Theorem 31.
For any integers1<k≤⌊n/2⌋ one has (36)12n2k+12n2-n2≤δCn1,2,3,…,k-1,k≤12n2k+12, if n=0,1(mod⁡2k), and (37)12n2k+12+12n2-n2≤δCn1,2,3,…,k-1,k≤12n2k+1,if n≠0,1(mod⁡2k).Proof.
Let us denote by{0,1,…,n-1} the vertices of G≔Cn(1,2,3,…,k-1,k).
It is easy to check that(38)diam⁡VG=n2kifn=0,1mod⁡2k,diam⁡VG=n2k+1ifn≠0,1mod⁡2k,and Corollary 10 gives the upper bounds.
In order to prove the lower bounds, assume first thatn is even (and then n/2-⌊n/2⌋=0).
Defineg1, g2 as the geodesics in G joining 0 and n/2 with g1∩V(G)={0,k,2k,…,k⌊n/(2k)⌋,n/2} and g2∩V(G)={0,n-k,n-2k,…,n-k⌊n/(2k)⌋,n/2}. If p is the midpoint of g1, then (39)δG≥dGp,g2=dGp,0,n2=12Lg1=12diam⁡VG.
Assume now thatn is odd (and then n/2-⌊n/2⌋=1/2) and let y be the midpoint of the edge [(n-1)/2,(n+1)/2].
Defineg1′, g2′ as the geodesics in G joining 0 and y with g1′∩V(G)={0,k,2k,…,k⌊n/(2k)⌋,(n-1)/2} and g2′∩V(G)={0,n-k,n-2k,…,n-k⌊n/(2k)⌋,(n+1)/2}. If p′ is the midpoint of g1′, then (40)δG≥dGp′,g2′=dGp,0,n2=12Lg1′=12diam⁡VG+12.


## 4. Conclusions

In this paper we study the hyperbolicity constant of an important class of networks: circulant graphs. We obtain several sharp inequalities for the hyperbolicity constant and in some cases we characterize the graphs for which the equality is attained.Theorem3 in Section 2 gives the precise value of the hyperbolicity constant of δ(Cn(a1)). Theorem 11 provides a sharp lower bound for δ(Cn(a1,a2,…,ak)) and characterizes the graphs for which the equality is attained. It is well known that a network is circulant if and only if its complement is circulant. Thus it is natural to study in this context the properties of general complement graphs. In Theorems 15 and 24 this kind of results for general networks appears and they are applied to circulant graphs in Corollary 25.We collect in Section3 several sharp inequalities for the hyperbolicity constant of a large class of circulant graphs. In Theorem 28 good lower and upper bounds for δ(Cn(1,a2,…,ak)) appear, which are improved in Theorems 29, 30, and 31 with additional hypothesis. Furthermore, we obtain the precise value of the hyperbolicity constant of many circulant networks (see Theorems 3, 11, and 29 and Corollary 25).



---

*Source: 723451-2015-11-02.xml*