In . J. Appl. Ma h. Compu . Sci., 2016, Vol. 26, No. 4, 855–870
DOI: 10.1515/amcs-2016-0061
AN ADVANCE IN INFINITE GRAPH MODELS FOR THE ANALYSIS OF
TRANSPORTATION NETWORKS
MART´
IN CERAa,∗,EUGENIO M. FEDRIANIb
aDepa men o Applied Ma hema ics I
Uni e si y o Se ille, ETSIA, C a. U e a km 1, ES-41013 Se ille, Spain
e-mail: [email p o ec ed]
bDepa men o Economics, Quan i a i e Me hods and Economic His o y
Pablo de Ola ide Uni e si y, C a. U e a km 1, ES-41013 Se ille, Spain
e-mail: [email p o ec ed]
This pape ex ends o in ini e g aphs he mos gene al ex emal issues, which a e p oblems o de e mining he maximum
numbe o edges o a g aph no con aining a gi en subg aph. I also ela es he new esul s wi h he co esponding si ua ions
o he ini e case. In pa icula , concep s om ‘ ini e’ g aph heo y, like he a e age deg ee and he ex emal numbe , a e
gene alized and compu ed o some speci ic cases. Finally, some applica ions o in ini e g aphs o he anspo a ion o
dange ous goods a e p esen ed; hey in ol e he analysis o ne wo ks and pe cola ion h esholds.
Keywo ds: in ini e g aph, a e age deg ee, ex emal p oblems, oad anspo ne wo k, pe cola ion.
1. In oduc ion
G aph heo y is a e y use ul ool in a ious ields
o human knowledge. Howe e , when ying o sol e
eal p oblems, scien is s may need o de elop he
exis ing heo y beyond he poin i has eached so a .
Fo ins ance, he analysis o con inuously inc easing
ne wo ks, ex emely complex sys ems, luids il e ing
h ough po ous ma e ials, e c. equi es he in ol emen o
in ini e g aphs and some p ope ies ha ha e hi he o been
de eloped only o he ini e case.
Maybe he mos clea example o his ac is he
a e age deg ee. In gene al, and no only in ex emal
g aph heo y, we can ind many p oblems in ol ing he
ela ionship be ween he numbe s o e ices and edges
o a g aph (see, e.g., Ce a e al., 2000; 2004, Yang e
al., 2002; Youse i-Aza ia e al., 2011), i.e., he a e age
deg ee. In some cases, many o hese p oblems could be
posed o in ini e g aphs.
We can ind in he li e a u e many pape s s udying
he p oblem o p o iding a de ini ion o he a e age
deg ee o in ini e g aphs (see S ein, 2011; S ein and
Zamo a, 2013; Wie man and Nao , 2005). Up o now, no
∗Co esponding au ho
o mal de ini ion has been ound. Indeed, i is no possible
o gi e a gene al de ini ion o he a e age deg ee o any
in ini e g aph.
On he basis o he abo e, his pape i s ly aims o
ela e he concep s o he in ini e g aph and he a e age
deg ee. In ac , we de ine he a e age deg ee o a amily
o in ini e g aphs ha we call a e age-measu able.
This de ini ion allows us o ex end o in ini e g aphs
he p oblem o de e mining he maximum numbe o
edges o a g aph no con aininga subg aph homeomo phic
o a comple e g aph. We s udy he ela ionship o his
p oblem wi h i s coun e pa in ini e g aphs.
No a ion and e minology no explici ly gi en he e
can be ound in heo e ical handbooks (Dies el, 2000;
Made , 1998b; Milko ´a, 2009).
1.1. Func ion d(p) o he ini e case. Gi en Fas
a ini e g aph, he ex emal numbe ex(n;F)deno es he
maximum numbe o edges o a g aph wi h n e ices no
con aining Fas a subg aph. This de ini ion induces he
mos gene al ype o ques ion we can s a e in ex emal
g aph heo y. I can be posed o ini e as well as
in ini e g aphs. The ques ion is whe he some in a ian
(e.g., edge-densi y, minimum deg ee, ch oma ic numbe
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM
856
M. Ce a and E.M. Fed iani
o a e age deg ee) has an in luence on he showing
up o subs uc u es o ano he g aph in a ian . In his
con ex , an impo an , well-known esul in ini e g aph
heo y implies ha la ge a e age deg ees in ini e g aphs
o ce la ge mino s and opological mino s (a subg aph
homeomo phic o a comple e g aph) (see Dies el, 2000).
The ex ension o hese p oblems om ini e g aphs o
in ini e g aphs is in e es ing in g aph heo y. Some o
hem can e en be ound o some ex emal p oblems (see
S ein, 2011; S ein and Zamo a, 2013).
Gi en a g aph G, le us deno e by (G)=|V(G)|
and e(G)=|E(G)| he ca dinals o he e ices and
edges o G, espec i ely. Then he a e age deg ee o Gis
d(G)=2e(G)
(G).
Now, we no e ha he unc ion
d(p) = in { :d(G)≥ −→ TKp⊆G},
s a ed by Made (1967),may be o mula ed in e ms o he
unc ion ex(n;TKp),i.e., in e ms o he numbe o edges
o a g aph wi h n e ices and no con aining a subg aph
homeomo phic o a comple e g aph ( opological clique).
P oposi ion 1. Le pbe a non-nega i e in ege . Then
d(p)=sup
n≥p2ex(n;TKp)
n.
P oo . W i e
d(n;TKp)=2ex(n;TKp)
n.
I
d(p)>sup
n≥p
{d(n;TKp)},
hen he e exi s a eal numbe such ha
d(p)> >sup
n≥p
{d(n;TKp)}.
Le us conside a g aph Gsa is ying d(G)≥ >
d(|V(G)|;TKp).Hence, TKp⊆Gand, he e o e, by
he de ini ion o d(p),d(p)≤ , bu his is no possible.
Thus,
d(p)≤sup
n≥p
{d(n;TKp)}.
To p o e he con e se inequali y, we suppose
ha he e exis s a posi i e in ege nsuch ha
d(p)<d(n;TKp).Now, we conside n∈Rsuch ha
d(p)<
n<d(n;TKp).The e o e, o e e y g aph G
wi h |V(G)|=n,i d(G)≥ n>d(p), hen (by he
de ini ion o d(p))Gcon ains a subg aph homeomo phic
o Kp.Hence, by he de ini ion o d(n;TKp),we would
ha e d(n;TKp)≤ n<d(n;TKp),bu his is no
possible, ei he . Thus, d(p)≥d(n;TKp) o all nand
he esul ollows. 
1.2. Pape objec i es and s uc u e. Bea ing in mind
he a o emen ioned esul , i we wan o ge exac alues
o he unc ion d(p),i is su icien o calcula e exac
alues o ex(n;TKp)wi h nbeing su icien ly la ge. In
o he wo ds, since he e exis s a necessi y o s udying
ex(n;TKp) o n ending o in ini e, we s a e he p oblem
o s udying his unc ion o in ini e g aphs.
Addi ionally, he p oblem o s udying he numbe o
edges in ela ion o he numbe o e ices in an in ini e
g aph has no sense. Bu his pape explains ha i is use ul
as a local concep when dealing wi h anspo ne wo ks.
This ac sugges s he possibili y o conside ing he idea
o de ining he concep o an a e age deg ee o in ini e
g aphs. This idea seems e en mo e in e es ing i we bea
in mind ha an in ini e g aph may be conside ed he limi
o ini e g aphs.
Taking in o accoun all hese ideas, we no e ha he
goal o he heo e ical pa o his pape is wo old. On
he one hand, we de ine an a e age deg ee o in ini e
g aphs inhe i ing he p ope ies o he a e age deg ee
o ini e g aphs. On he o he hand, we gene alize he
unc ion d(p) o ini e and in ini e g aphs and we p o e
ela ionships be ween bo h unc ions.
The nex sec ion deals wi h he gene aliza ion o he
a e age deg ee o in ini e g aphs. The inc easing concen-
ic sequences a e de ined and he concep o he a e age-
measu able g aph is in oduced. Besides, h ee in ini e
amilies o a e age-measu able g aphs a e p esen ed.
The ollowing sec ion is de o ed o ex ending he
ex emal unc ion ex(n;TKp). The unc ion d∞(p)is
de ined and bounded by he co esponding‘ ini e e sion’.
Some o he heo e ical esul s a e p o ed, and hey
p o ide us wi h exac alues o d∞(p)when 1≤p≤5.
Finally, we apply he s udied concep s o he
anspo a ion o dange ous goods, paying special
a en ion o complex ne wo ks and pe cola ion. The pape
concludes wi h a b ie summa y.
2. A e age-measu able g aphs
In his sec ion, we de ine he a e age deg ee o a amily
o in ini e g aphs ha we call a e age-measu able.We
s a wi h a sequence o ini e g aphs, and he a e age
deg ee o in ini e g aphs will inhe i he p ope ies o
he a e age deg ee o he ini e case (see Ba ooah and
Hespanha, 2008; Wie man and Nao , 2005; Zemanian,
1988). We a e abou o p o e ha ees a e examples
o a e age-measu able g aphs. On he o he hand, we
in oduce ano he amily o g aphs, called quasi- ini e
g aphs, ha a e also p o ed o be a e age-measu able.
To achie e hese goals we need some no a ion and
de ini ions.
De ini ion 1. Le Gbe an in ini e, locally ini e g aph,
and le {Gn}n∈Nbe a sequence o ini e subg aphs o
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM
An ad ance in in ini e g aph models o he analysis o anspo a ion ne wo ks
857
G. We say ha {Gn}n∈Nis an inc easing concen ic se-
quence (ICS) o Gi he ollowing h ee condi ions a e
sa is ied:
•Gn⊂Gn+1 o all n,
•∂Gn∩∂Gn+1 =∅ o all n,
•∪
n∈NGn=G,
whe e ∂Gn=V(Gn)−V(Gn−1)Gdeno es he bound-
a y o Gn.
We no e ha , gi en an in ini e g aph Gand ∈G,
i is always possible o ind an ICS. In ac , i we conside
he subg aphs Gn( )={u∈V(G):d(u, )≤n}G,
whe e d(u, )deno es he dis ance be ween he e ices u
and , i is easy o p o e ha he sequence {Gn( )}n∈N
sa is ies he condi ions desc ibed abo e o being an ICS
o G.
De ini ion 2. Gi en an in ini e, locally ini e g aph G, we
de ine he in e io -a e age deg ee o Gas
d∞(G) = in lim in
n→+∞d(Gn( )) : ∈G,
whe e d(Gn)is he a e age deg ee o each ini e g aph
Gn( ).
On he o he hand, we de ine he supe io -a e age
deg ee o Gas
d∞(G)=suplim sup
n→+∞
d(Gn( )) : ∈G.
De ini ion 3. Le Gbe an in ini e, locally ini e
g aph. Gis said o be a e age-measu able g aph i
d∞(G)=d∞(G)<+∞.Besides, in his case, we de ine
he a e age deg ee o Gas d∞(G)=d∞(G)=d∞(G).
Example 1. Le Hbe he ee shown in Fig. 1, whe e he
e ex uis a oo and he deg ee o he e ices o each
le el equals i s p edecesso plus one ( wo o he i s and
second le els).
           
  






 

 

 

 

 

 

 

 

 

 



Fig. 1. T ee Hwi h an inc easing deg ee.
I we conside he ICS {Hn(u)}n∈N,i is easy o
check ha , o e e y posi i e in ege n,
|V(Hn(u))|=2! + ···+(n+2)!
2.
On he o he hand, aking in o accoun ha each ini e
subg aph Hn(u)o H is a ee,
|E(Hn(u))|=|V(Hn(u))|−1,
and, he e o e,
lim
n→+∞2·|E(Hn(u))|
|V(Hn(u))|= 2 lim
n→+∞1−1
|V(Hn(u))|=2.
Howe e , his p ope y (p o ed o he e ex u) is, in ac ,
ue o e e y e ex o H. Mo eo e , his p ope y is ue
o e e y ee. 
Theo em 1. E e y in ini e, locally ini e ee Tis a e age-
measu able and d∞(T)=2.
The ollowing example shows a non-a e a-
ge-measu able g aph.
Example 2. Le us conside he g aph G(see Fig. 2),
ob ained om he g aph Hin he p e ious example and
sa is ying
∂G1( )=K3
and
|E(∂Gn( ))|=n|V(Gn( ))| o n≥2.
           
  






 

 

 

 

 

 

 

 

 

 
















½




¾











Fig. 2. G aph Gob ained om H.
By induc ion, i is easy o see ha
n|V(Gn( ))|≤|V(∂Gn( ))|
2
and, he e o e, i is possible o p oduce such a g aph G.
On he o he hand, om he cons uc ion o G,
|V(Gn( ))|=2! + ···+(n+2)!
2
and
|E(Gn( ))|=|V(Gn( ))|−1+3+···
+2|V(G2( ))|+···+n|V(Gn( ))|.
Now, le Mbe he g aph designed in such a way ha
V(M)=V(H)∪V(G)∪{w}
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM
858
M. Ce a and E.M. Fed iani
 


 

Fig. 3. G aph Mob ained om Hand G.
and
E(M)=E(H)∪E(G)∪{(u, w),( ,w)}
(see Fig. 3).
We a e going o s udy he sequences {Mn(u)}n∈N
and {Mn( )}n∈N.By he de ini ion o Mn(u), o n≥2,
|V(Mn(u))|=|V(Hn(u))|+|V(Gn−2( ))|+1
and
|E(Mn(u))|=|E(Hn(u))|+|E(Gn−2( ))|+2.
To de e mine he limi o he sequence {d(Mn(u))}n≥2,
i is su icien o analyze he beha io o he quo ien
|E(Mn(u))|/|V(Mn(u))|.By applying he well-known
S olz heo em o sequences
|E(Mn+1(u))|−|E(Mn(u))|
|V(Mn+1(u))|−|V(Mn(u))|
=
(n+3)!
2+(n+1)!
2+(n−1) ·2! + ···+(n+1)!
2
(n+3)!
2+(n+1)!
2
=1+
(n−1) ·2! + ···+(n+1)!
2
(n+3)!
2+(n+1)!
2
.
I we apply again he S olz heo em, we ge
lim
n→+∞
(n−1)(2! + ···+(n+1)!)
(n+3)!+(n+1)! =0.
I ollows ha
lim
n→+∞2|E(Mn(u))|
|V(Mn(u))|=2
and, he e o e, d∞(M)≤2.
Now we analyze wha happens wi h he sequence
{Mn( )}n∈N:
|V(Mn( ))|=|V(Hn−2(u))|+|V(Gn( ))|+1
and
|E(Mn( ))|=|E(Hn−2(u))|+|E(Gn( ))|+2.
We apply he S olz heo em o compu e he limi o he
a e age deg ee o each subg aph Mn( ):
|E(Mn+1( ))|−|E(Mn( ))|
|V(Mn+1( ))|−|V(Mn( ))|
=1+
(n+1)·2! + ···+(n+3)!
2
(n+3)!
2+(n+1)!
2
.
By applying he S olz heo em again,
lim
n→+∞
(n+ 1)(2! + ···+(n+3)!)
(n+3)!+(n+1)! =+∞.
Hence
lim
n→+∞2·|E(Mn(u))|
|V(Mn(u))|=+∞
and, he e o e, d∞(M)=+∞.Thus,
d∞(M)≤2< d∞(M)=+∞,
and Mis non-a e age-measu able. 
2.1. Quasi- ini e g aphs. Nex we de ine a amily o
in ini e g aphs which a e a e age-measu able when hei
maximal deg ee is bounded.
De ini ion 4. Le Gbe an in ini e, locally ini e g aph.
The ICS {Gn}n∈Nsa is ies he so-called bounda y condi-
ion when
lim
n→+∞
|V(∂Gn)|
|V(Gn)|=0.
Rema k 1. The bounda y condi ion
lim
n→+∞
|V(∂Gn)|
|V(Gn)|=0
is equi alen o
lim
n→+∞
|V(Gn−1)|
|V(Gn)|=1,
since
|V(∂Gn)|
|V(Gn)|=|V(Gn)|−|V(Gn−1)|
|V(Gn)|
=1−|V(Gn−1)|
|V(Gn)|.
De ini ion 5. Le Gbe an in ini e, locally ini e g aph. G
is said o be quasi- ini e i he e exis s a e ex ∈Gsuch
ha he ICS {Gn( )}n∈Nsa is ies he bounda ycondi ion.
The ollowing esul shows ha he p e ious
de ini ion does no depend on he chosen e ex, i.e., i
he e exis s a e ex o which {Gn( )}n∈Nsa is ies he
bounda y condi ion, hen i is sa is ied o all .
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM
An ad ance in in ini e g aph models o he analysis o anspo a ion ne wo ks
859
Lemma 1. Le Gbe an in ini e, locally ini e g aph. I
Gis quasi- ini e, hen he sequence {Gn( )}n∈Nsa is ies
he bounda y condi ion o all ∈G, i.e.,
lim
n→+∞
|V(∂Gn( ))|
|V(Gn( ))|=0.
P oo . Le Gbe a quasi- ini e g aph and 0bea e ex
such ha he ICS {Gn( 0)}n∈Nsa is ies he bounda y
condi ion. Gi en ∈G, we deno e by he dis ance
be ween and 0( =d( , 0)). Taking in o accoun
Rema k 1, i is su icien o p o e he equali y
lim
n→+∞
|V(Gn−1( ))|
|V(Gn( ))|=1
o show ha he bounda y condi ion is sa is ies.
Consequen ly, we no e ha , o n≥ +1,
Gn− −1( 0)⊆Gn−1( ),
Gn( )⊆Gn+ ( 0).
Hence
|V(Gn−1( ))|
|V(Gn( ))|≥|V(Gn− −1( 0))|
|V(Gn+ ( 0))|.
Fu he mo e,
|V(Gn− −1( 0))|
|V(Gn+ ( 0))|
=|V(Gn− −1( 0))|
|V(Gn− ( 0))|
|V(Gn− ( 0))|
|V(Gn− +1( 0))|
···|V(Gn+ −1( 0))|
|V(Gn+ ( 0))|,
bu |V(Gn− −1( 0))|
|V(Gn− ( 0))|
−−−−→
n→+∞1
.
.
.
|V(Gn+ −1( 0))|
|V(Gn+ ( 0))|
−−−−→
n→+∞1.
Finally,
1≥lim
n→+∞
|V(Gn−1( ))|
|V(Gn( ))|
≥lim
n→+∞
|V(Gn− −1( 0))|
|V(Gn+ ( 0))|=1.
Thus,
lim
n→+∞
|V(Gn−1( ))|
|V(Gn( ))|=1,
and he esul ollows. 
Rema k 2. By easoning as in Lemma 1, we ge
lim
n→+∞
|V(Gn( ))|
|V(Gn+k( ))|=1
o all posi i e in ege k.
The p e ious lemma can be gene alized o o he
sequences. In ac , gi en a ini e G0⊂G, we conside he
ICS {Gn(G0)}n≥0as he sequence de ined as ollows:
Gn(G0)={u∈V(G):d(u, G0)≤n}G.
Theo em 2. Le Gbe an in ini e, locally ini e g aph.
Then Gis quasi- ini e i and only i he e exis s a ini e
subg aph G0⊂Gsa is ying he bounda y condi ion, ha
is o say,
lim
n→+∞
|V(∂Gn(G0))|
|V(Gn(G0))|=0.
Besides, i he a o emen ioned asse ion is ue, hen he
bounda y condi ion is sa is ied o e e y ini e subg aph
G0⊂G.
P oo . Le Gbe an in ini e, quasi- ini e g aph, and G0⊂
Gbe a ini e subg aph. We a e p o ing ha
lim
n→+∞
|V(Gn−1(G0))|
|V(Gn(G0))|=1.
Fo his pu pose, le us conside 0∈V(G0)and deno e
by he diame e o G0( =diam(G0)). Consequen ly,
Gn−1( 0)⊆Gn−1(G0)
Gn(G0)⊆Gn+ ( 0)
o all n. I ollows ha
|V(Gn−1(G0))|
|V(Gn(G0))|≥|V(Gn−1( 0))|
|V(Gn+ ( 0))|.
Bea ing in mind he inequali y
|V(Gn−1(G0))|
|V(Gn(G0))|≤1
and by applying Rema k 2,
1≥lim
n→+∞
|V(Gn−1(G0))|
|V(Gn(G0))|
≥lim
n→+∞
|V(Gn−1( 0))|
|V(Gn+ ( 0))|=1.
The e o e,
lim
n→+∞
|V(Gn−1(G0))|
|V(Gn(G0))|=1.
In o de o p o e he con e se implica ion, we
suppose ha he e exis s a G0such ha he sequence
{Gn(G0)}sa is ies he bounda y condi ion. Since ha
0∈V(G0)and =diam(G0),
Gn− −1(G0)⊆Gn−1( 0)
and
Gn( 0)⊆Gn(G0).
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM

860
M. Ce a and E.M. Fed iani
Hence
|V(Gn−1( 0))|
|V(Gn( 0))|≥|V(Gn− −1(G0))|
|V(Gn( 0))|.
By easoning as in Rema k 2, we see ha
lim
n→+∞
|V(Gn− −1(G0))|
|V(Gn(G0))|=1,
so ha
lim
n→+∞
|V(Gn−1( 0))|
|V(Gn( 0))|=1.

Now, we a e going o p o e ha e e y
quasi- ini e g aph wi h a bounded maximal deg ee is
a e age-measu able.
Theo em 3. Le Gbe an in ini e, locally ini e g aph wi h
Δ(G)<+∞.I Gis quasi- ini e, hen Gis a e age-
measu able.
P oo . Le Gbe an in ini e g aph wi h maximal deg ee
Δ(G)=Δ<+∞.Gi en ∈G, we conside he
sequence Gn=Gn( ) o n∈N.Since Δ(G)<+∞,
we know ha d(Gn)≤2Δ.To p o e ha {d(Gn)}is
con e gen ,we check ha , in ac , i is a Cauchy sequence,
ha is,
lim
n→+∞|d(Gn+1)−d(Gn)|=0.
Now, we conside he sequence {sn}de ined as
ollows:
sn=
|E(Gn+1)|
|V(Gn+1)|−|E(Gn)|
|V(Gn)|
=
|E(Gn+1)|·|V(Gn)|−|E(Gn)|·|V(Gn+1)|
|V(Gn)|·|V(Gn+1)|
.
I we se
E(∂Gn,∂G
n+1)={(wn,w
n+1)∈E(G):
wn∈∂Gn,w
n+1 ∈∂Gn+1},
hen (see Fig. 4)
|E(Gn+1)|=|E(Gn)|+|E(∂Gn,∂G
n+1)|
+|E(∂Gn+1)|.
Thus,
sn=
1
|V(Gn)|·|V(Gn+1)|
|V(Gn)||E(Gn)|+|E(∂Gn,∂G
n+1)|
+|E(∂Gn+1)|−···−|E(Gn)|·|V(Gn+1)|
≤|E(Gn)|||V(Gn)|−|V(Gn+1)||
|V(Gn)|·|V(Gn+1)|
+|E(∂Gn,∂G
n+1)|
|V(Gn+1)|+···+|E(∂Gn+1)|
|V(Gn+1)|.

wn

wn+1
Gn
∂Gn
∂Gn+1
Fig. 4. Edge decomposi ion E(Gn+1).
Howe e ,
|E(Gn)|||V(Gn)|−|V(Gn+1)||
|V(Gn)|·|V(Gn+1)|≤Δ·|V(∂Gn+1)|
|V(Gn+1)|,
|E(∂Gn,∂G
n+1)|
|V(Gn+1)|≤Δ·|V(∂Gn)|
|V(Gn+1)|≤Δ·|V(∂Gn)|
|V(Gn)|,
and |E(∂Gn+1)|
|V(Gn+1)|≤Δ·|V(∂Gn+1)|
|V(Gn+1)|.
Hence
sn≤Δ·|V(∂Gn+1)|
|V(Gn+1)|+Δ·|V(∂Gn)|
|V(Gn)|
+Δ·|V(∂Gn+1)|
|V(Gn+1)|.
As
lim
n→+∞
|V(∂Gn)|
|V(Gn|=0,
we ge
lim
n→+∞sn=0
and, he e o e, he sequence {d(Gn)}n∈Nis con e gen .
Finally, o each d∞(G)=d∞(G),we a e going o
p o e ha , o all u∈V(G),
lim
n→+∞
|E(Gn(u))|
|V(Gn(u)|= lim
n→+∞
|E(Gn( ))|
|V(Gn( )|= .
Fo his pu pose, we conside u∈V(G)and
=dG(u, ).Acco dingly,
n
=
|E(Gn(u))|
|V(Gn(u))|−|E(Gn( )|
|V(Gn( )|
=
|E(Gn(u))||V(Gn( ))|−|E(Gn( ))||V(Gn(u))|
|V(Gn(u))||V(Gn( ))|
.
Besides, aking in o accoun ha
Gn− ( )⊆Gn(u)⊆Gn+ ( )
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM
An ad ance in in ini e g aph models o he analysis o anspo a ion ne wo ks
861
o n≥ , we ha e ha
n≤
1
|V(Gn− ( ))||V(Gn( ))|
×(|E(Gn+ ( ))||V(Gn( ))|
−|E(Gn( ))||V(Gn− ( ))|)
×
|E(Gn+ ( ))|
|V(Gn− ( ))|−|E(Gn( ))|
|V(Gn( ))|
.
Since
lim
n→+∞
|V(Gn( ))|
|V(Gn+1( ))|=1
and
|E(Gn+ ( ))|
|V(Gn− ( ))|=|E(Gn+ ( ))|
|V(Gn+ ( ))|
|V(Gn+ ( ))|
|V(Gn+ −1( ))|
×|V(Gn− +1( ))|
|V(Gn− ( ))|,
we conclude ha
lim
n→+∞
|E(Gn+ ( ))|
|V(Gn− ( ))|=
and, he e o e, lim
n→+∞ n=0.
Now, we no e ha he condi ion Δ(G)<+∞is
necessa y in his heo em, as we can see wi h he g aph G
om Fig. 5: Gis quasi- ini e bu no a e age-measu able.
      
    
  


Æ



Æ



Æ






Æ






½

¾

¿



Fig. 5. Quasi- ini e g aph wi h Δ(G)=+∞, bu non-a e age-
measu able.
This g aph is de ined in such a way ha he subg aph
∂Gnis a comple e g aph o size 2n+1, o n≥1.Thus,
|V(Gn( ))|=1+3+5+···+(2n+1)
and
|E(Gn( ))|=3+5+···+(2n+1)
+3
2+5
2+···
+2n+1
2.
Gis quasi- ini e because
lim
n→+∞
|V(∂Gn( ))|
|V(Gn( ))|
= lim
n→+∞
2n+1
1+3+5+···+(2n+1) =0.
In o de o ge he limi o |E(Gn( ))|/|V(Gn( ))|,we
apply he S olz heo em:
|E(Gn+1( ))|−|E(Gn( ))|
|V(Gn+1( ))|−|V(Gn( ))|
=2n+3+2n+3
2
2n+3 =+∞.
Thus, d∞(G)=+∞and Gis no a e age-measu able.
On he o he hand, we conside he g aph H om
Example1 o indana e age-measu able g aph which is
no quasi- ini e. Ac ually, since His a ee, his g aph is
a e age-measu able; howe e , i is no quasi- ini e:
|V(∂Hn(u))|
|V(Hn(u))|=|V(Hn(u))|−|V(Hn−1(u))|
|V(Hn(u))|
=(n+2)!
2! + ···+(n+2)!.
By applying he S olz heo em,
lim
n→+∞
(n+3)!−(n+2)!
(n+3)! = lim
n→+∞
n+2
n+3 =1=0
and, he e o e, he sequence {Hn(u)}does no sa is y he
bounda y condi ion, and hence His no quasi- ini e.
2.2. Pe iodic g aphs. Now, we a e going o show
ha pe iodic g aphs a e quasi- ini e. These g aphs
a e e y use ul because hey a e equen and easily
compu ed. We can ind examples o pe iodic g aphs
in iling and pa e ns (G ¨unbaum and Shepha d, 1987)
o Cayley diag ams (Cayley, 1895; F uch , 1938), and
hey e en appea as he esul an g aphs o sol ing linea
sys ems (Baude on, 1989).
He e we ecall some p io esul s on pe iodic g aphs.
We deno e by C he uni squa e [0,1] ×[0,1] ⊂R2,and
we de ine a cellula g aph as he g aph sa is ying V(G)⊂
Cwi h no isola ed e ices. Thus, gi en a cellula g aph
G, we de ine he 2-dimensional pe iodic g aph (MG)as
he g aph ob ained om Gas ollows:
V(MG)=τ(m,n)( ): ∈V(G)and (m, n)∈Z2,
E(MG)=(τ(m,n)(u),τ
(m,n)( )) :
(u, )∈E(G)and (m, n)∈Z2,
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM
862
M. Ce a and E.M. Fed iani
whe e τ(m,n)deno es he ansla ion by ec o (m, n)in
he plane.
I MGis a 2-pe iodic g aph gene a ed by he cellula
g aph G, hen we de ine he 8-neighbo s o Gas he
subg aphs τ(i,j)(G)o MGsuch ha i∈{−1,0,1}and
j∈ {−1,0,1}, wi h (i, j)=(0,0).
Gi en a cellula g aph Gand he 2-pe iodic g aph
gene a ed by G, MG,we de ine he n-squa e o cen e G
and adius n(nG) as he subg aph o MG:
nG=τ(i,j)(G):(i, j)∈Z2,max{|i|,|j|}≤n.
We a e p o ing ha , in ac , he 2-pe iodic g aphs
a e quasi- ini e and a e age-measu able (since hey ha e
a bounded maximal deg ee).
Theo em 4. E e y in ini e, pe iodic, connec ed g aph
MGgene a ed by he cellula g aph Gis quasi- ini e and
a e age-measu able.
P oo . Le Gbe a cellula g aph and M=MGbe he
2-pe iodic g aph gene a ed om G. By Theo em 2, i is
su icien o p o e ha
lim
n→+∞
|V(∂Mn(G))|
|V(Mn(G))|=0
o show ha Mis quasi- ini e. We ecall ha
Mn(G)=u∈V(M):d(u, G)M≤nM.
Conside
d=max{d(u, G):u∈Gi,1≤i≤8},
whe e Gia e he 8-neighbo s o G. Fi s ly, o all n≥d,
i is easily seen ha (see Fig. 6)
n
dG⊆M
n(G)⊆nG,
because i ∈n
dG, hen (see Fig. 7)
d(u, G)≤d+d(u, n
d−1G)≤···≤dn
d≤n.
Acco dingly,
|V(∂Mn(G))|
|V(Mn(G))|
≤|V(∂Mn(G))|
|V(n
dG)|≤|V(∂Mn(G))|
2n
d+1
2|V(G)|
.
On he o he hand, o all n≥1,le us conside
k(n)=|V(∂Mn(G))|.As
V(Mn(G)) =
n

i=0
V(∂Mi(G)) ⊆V(nG),


















      























½









Fig. 6. Chain o inclusions o Mn(G).
    


























½

Fig. 7. n
dG⊆M
n(G).
we ha e
sn=k(1) + k(2) + ···+k(n)≤(2n+1)
2|V(G)|.
Suppose ha
lim sup
n→+∞
k(n)
n2=l,
wi h l>0.By applying he S olz heo em o he quo ien
sn/(2n+1)
2,we ge ha
sn+1 −sn
(2n+3)
2−(2n+1)
2=k(n+1)
8n+9
=k(n+1)
(n+1)
2
(n+1)
2
8n+9
and, he e o e,
lim sup
n→+∞
sn
(2n+1)
2|V(G)|
=1
|V(G)|lim sup
n→+∞
k(n+1)
(n+1)
2
(n+1)
2
8n+9 =+∞.
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM
An ad ance in in ini e g aph models o he analysis o anspo a ion ne wo ks
863
Bu his is no possible, because we we e assuming ha
sn
(2n+1)
2|V(G)|≤1.
Consequen ly,
lim
n→+∞
k(n)
n2=0
and, he e o e,
lim
n→+∞
|V(∂Mn(G))|
2n
d+1
2|V(G)|
≤1
|V(G)|lim
n→+∞
k(n)
n2
n2
2n
d−1+1
2=0.
Thus
lim
n→+∞
|V(∂Mn(G))|
|V(Mn(G))|=0
and Mis quasi- ini e. Besides, since Mis a 2-pe iodic
g aph, he asse ion Δ(M)<+∞is sa is ied, and (by
applying Theo em 3) Mis a e age-measu able. 
Now, we p esen an illus a ion o a 2-pe iodic g aph.
Example 3. We conside he 2-pe iodic g aph M
gene a ed by he cellula g aph Gas in Fig. 8.



 


  





 























































































































































































Fig. 8. Pe iodic g aph wi h he a e age deg ee 8
3.
Since Mis connec ed, by applying Theo em 4, we
deduce ha his g aph is a e age-measu able. Le us
conside he sequence {Mn(G)}.Since he sequence
{d(Mn(G))}is con e gen , we know ha
lim
n→+∞d(Mn(G)) = lim
n→+∞d(M2n(G)).
On he o he hand,
|V(M2n(G))|=5+16+6(4+8+···+2
n)
and
|E(M2n(G))|=4+16+8(4+8+···+2
n)
and, he e o e, by applying S olz Theo em,
lim
n→+∞d(M2n(G)) = 8
3.

Rema k 3. In in e connec ion ne wo ks, i is impo an
o con ol hei beha io when edges a e subdi ided o
con ac ed. Taking in o accoun he de ini ion o an
a e age deg ee o in ini e g aphs ha we ha e jus
in oduced, i is s aigh o wa d o check ha i we
subdi ide one o mo e edges in a g aph, he a e age
deg ee o he esul ing g aph is less han o equal o he
o iginal.
In he ollowing example (Fig. 9), i is easy o check
ha he a e age deg ee is ou . I subdi isions o each
edge a e pe o med (Figu e 10), we ob ain a g aph wi h a
smalle a e age deg ee ( he one shown in Fig. 8).
Fig. 9. Pe iodic g aph wi h he a e age deg ee 4.
Fig. 10. Pe iodic g aph wi h he a e age deg ee 8
3.
In he g aph displayed in Fig. 11 we can obse e
he beha io o he a e age deg ee when pe o ming
con ac ions o edges.
Ano he kind o pe iodic g aph is he 1-dimensional
case. This g aph M1
Gis gene a ed by a cellula g aph G
and ho izon al ansla ionsGio he g aph G(see Fig. 13).
He e we deno e by i he ansla ed e ex o in Gi, o
all in ege s iand all ∈V(G).
Now, we a e able o o mula e a gene al esul .
Theo em 5. Le Gbe a ini e cellula g aph. I M1
Gis
connec ed, hen i is quasi- ini e and, he e o e, a e age-
measu able.
B ough o you by | Biblio eca de la Uni e sidad de Se illa
Au hen ica ed
Download Da e | 8/29/17 1:13 PM