(k;+){Distan e-Hereditary Graphs
Sera no Ci erone Gabriele Di Stefano
DipartimentodiIngegneria Elettri a,
Universita degliStudidell'Aquila
I-67040Montelu odi Roio,L'Aquila, Italy
f i erone,gabrieleging.univaq.it
Abstra t
In this work we introdu e, hara terize, and provide algorithmi results
for (k;+){distan e-hereditary graphs, k 0. These graphs an be used
to modelinter onne tion networks withdesirable onne tivityproperties;
a network modeled as a (k;+){distan e-hereditary graph an be
hara -terizedas follows: if some nodes havefailed, as long as two nodes remain
onne ted, the distan e between these nodes in the faulty graph is bounded
bythedistan einthenon-faultygraph plusaninteger onstantk. The lass
of all these graphs is denoted by DH(k;+). By varying the parameter k,
lassesDH (k;+)in ludeallgraphsand formahierar hythatrepresentsa
parametri extensionofthewell-known lassofdistan e-hereditarygraphs.
Keywords: Inter onne tion networks, dilation number, distan e-hereditary
graphs, hara terization of graph lasses, forbidden subgraphs, re ognition
al-gorithms.
Apreliminaryversionofthispaperhasbeenpresentedatthe27thInternationalWorkshop
onGraph-Theoreti Con epts in ComputerS ien e (WG'01), June 14-16, Boltenhagen,2001
(see[5℄).
PartiallysupportedbytheHumanPotentialProgrammeoftheEuropeanUnionunder ontra t
no. HPRN-CT-1999-00104(AMORE)andbytheItalianMURSTProje t\TeoriadeiGra ed
Afundamentalprobleminanyparallelordistributedsystem istheeÆ ient
om-muni ation of data between pro essors. Su h eÆ ien y depends on the routing
s heme de ned over the system, that is the set of paths used to route data, one
path for ea h possible pair of pro essors. The eÆ ien y of a routing s heme is
meanly measured in terms of its stret h fa tor and dilation. The stret h fa tor
(dilation)isthemaximum ratio(di eren e)between thelengthofapath de ned
by the s heme and the shortest path between the same pair of pro essors.
In this work we are interested innetworks inwhi hrouting s hemes oin ide
withshortest pathsandnode failuresmayo ur. Distan esare always omputed
by means of shortest paths in the subnetwork that is indu ed by the non-faulty
omponents. In this ontext, the de rease of the eÆ ien y of the ommuni ation
onlydepends onthe topology of the networks. Tomeasure this eÆ ien y
degra-dation, some parameters about the topology an be de ned. In [8℄ the authors
de nedthenotionofstret hnumber,whileinthispaperweintrodu ethedilation
number of a graph G. It is de ned as the smallest k su h that G 2 DH(k;+),
where a network modeled as a graph belonging to the lass DH(k;+) an be
hara terized asfollows: if some nodes have failed, as long as two nodes remain
onne ted, the distan e between these nodes in the faulty graph is bounded bythe
distan einthenon-faultygraph plusaninteger onstantk. ElementsofDH(k;+)
are alled (k;+){distan e-hereditary graphs. The name ismotivated by the fa t
thatthewell-known lassofdistan e-hereditarygraphs[18,19℄ orrespondstothe
lassDH(0;+). So, by varyingthe parameterk, lassesDH(k;+): (1)in ludeall
graphs, (2) form a hierar hy that represents a parametri extension of
distan e-hereditary graphs. Given the relevan e of (k;+){distan e-hereditary graphs in
the area of ommuni ation networks, our purpose is to provide hara terization
and algorithmi resultsabout the introdu edgraphs.
Relatedworks. Inliteraturethere areseveralpapers devotedtofault-tolerant
network design, mainly starting from a given desired topology and introdu ing
fault-toleran eto it(e.g., see [4, 16,20℄).
Papers [8, 9℄ present several results about (k;){distan e-hereditary graphs,
i.e., graphs whose indu ed distan e is bounded by a multipli ative fa tor k.
In [14℄, astudy about similar on epts isperformed: they give hara terizations
for graphs in whi h no delay o urs in the ase that a single node fails. These
graphs are alled self-repairing. In [10℄, authors introdu e and hara terize new
lassesof graphs that guarantee onstant stret hfa tors k even when amultiple
numberofedges havefailed. Ina rst step,they donot limitthenumberofedge
faultsatall,allowingforunlimited edge faults. Se ondly,they examine themore
realisti ase wherethenumberof edgefaultsisbounded by avalue`. The
orre-spondinggraphs are alledk{self-spanners and (k;`){self-spanners, respe tively.
graphs [18, 19℄: they have been investigated to design inter onne tion network
topologies[7,12,13℄, and several papers have been devoted tothem (see [3℄and
referen es therein).
Results. First, we formally introdu e (k;+){distan e-hereditary graphs and
provide some preliminary results. An initial hara terization is given in terms
of the dilation number. Then, we remark relationships between (k;
){distan e-hereditary graphs and (k;+){distan e-hereditary graphs. Starting from these
observations, we introdu e the notion of twin graph G
of an arbitrary graph
G. This graph has the remarkable property that G 2 DH(k;+) if and only if
G
2DH(k;+). Thankstothis notion, weare able toprovidea hara terization
of graphs G in DH(k;+) based on y le- hord onditions of its twin graph G
.
Sin e we also show that the re ognition problem for the new graph lasses is
Co-NP- omplete(fork not xed), thenweinvestigateinmoredetailthesmallest
lass among the new ones, i.e., lass DH(1;+). In this ontext, our main result
onsistsof listingall the forbiddenindu ed subgraphs of every G2DH(1;+). A
theoreti al onsequen e of this hara terization is that the re ognition problem
of lass DH(1;+) an besolved in polynomialtime.
This paper is organized as follows. Notation and basi on epts used in this
workare given inSe tion 2,while Se tion3formallyintrodu es(k;
+){distan e-hereditary graphsand providessomepreliminaryresults. Se tions 4 and5 study
graphsin DH(k;+): the former introdu es and uses the notion of twin graph to
hara terize graphs in DH(k;+), and the latter states the Co-NP- ompleteness
result. Se tions 6 and 7 study graphs in DH(1;+): the former hara terizes
graphsinDH(1;+)by listingforbidden indu ed subgraphs, whilethe latter uses
this hara terization toprovideapolynomialtimere ognition. Finally,Se tion8
on ludes the paperby listingsome open problems.
2 Notation and basi on epts
In this work we onsider nite, simple, loopless, undire ted and unweighted
graphs G = (V;E) with node set V and edge set E. We use standard
termi-nologiesfrom[3, 17℄, some of whi hare brie y reviewed here.
jGj denotes the ardinality of V. A subgraph of G is a graph having all its
nodes and edges in G. Given a subset S of V, the indu ed subgraph hSi of G is
themaximalsubgraph ofGwithnode setS. G S isthesubgraphof Gindu ed
by V nS; whenS =fxg, we writeG x insteadof G fxg.
If x is a node of G, by N
G
(x) we denote the neighbors of x in G, that is,
the set of nodes in G that are adja ent tox, and by N
G
[x℄we denote the losed
neighborhood of x, that is N
G (x)[fxg. Moreover, N G (S) = S u2S N G (u) and
e d f
Figure 1: The hord distan e of this y le C
6
is 2 be ause nodes d and e are
onse utive and every hord is in ident to one of them. Moreover, there is no
other set with less then 3 nodes with the sameproperties.
N G [S℄ = S u2S N G
[u℄. The degree of x is denoted by deg
G
(x) and it is equal to
jN
G
(x)j. SV is anindependent set in Gif (x;y)62E, for allx;y2S.
Two nodes v and v 0
of G are twins in G if they have the same neighborhood
in G; we distinguish between false twins when N
G
(v) = N
G (v
0
) and true twins
whenN G [v℄=N G [v 0
℄. Ifu2 V, operation (G;u) (see [3℄) extends G by adding
afalsetwin ofu;theresultinggraphisG 0 =(V [fu 0 g;E[f(u 0 ;v)jv 2N G (u)g).
A sequen e of pairwise distin t nodes (x
0 ;x 1 ;:::;x n ) is a path in G if (x i ;x i+1
) 2 E for 0 i < n. The length of a path p = (x
0
;:::;x
n
) is n,
whereas jpj denotes the number of its nodes. A path (x
0 ;:::;x n ) is an indu ed pathifhfx 0 ;:::;x n
gihasn edges. Twonodes xand yofGare onne ted ifthere
is a path from x to y in G. A graph G is onne ted if, for ea h pair of nodes x
andy of G,x and y are onne ted. A bi onne ted omponent of Gisa subgraph
of Gwhi h remains onne ted even if we delete any of itsnodes.
The length of a shortest path between two nodes x and y in G is alled
distan e and is denoted by d
G
(x;y); moreover, the length of a longest indu ed
path between the same nodes is denoted by D
G
(x;y). We use symbols P
G (x;y)
and p
G
(x;y) to denote a longest and a shortest indu ed path between x and y,
respe tively. Sometimes,whennoambiguityo urs,weuseP
G
(x;y)andp
G (x;y)
todenote the sets of nodes belongingto the orresponding paths.
A y leC n inGisapath(x 0 ;:::;x n 1 )wherealso(x 0 ;x n 1 )2E. Twonodes x i andx j are onse utiveinC n
ifj (i+1)modnori(j+1)modn. A hord
of a y le isan edge joiningtwo non- onse utive nodes in the y le. H
n
denotes
an hole, i.e., a y le with n nodes and without hords. The hord distan e of
a y le C
n
is denoted by d(C
n
), and it is de ned as the minimum number of
onse utive nodes in C
n
su h that every hord of C
n
is in identto some of su h
nodes (see Fig. 1). We de ne d(H
n )=0.
IfxandyaretwonodesofGsu hthatd
G
(x;y)2,thenfx;ygisa y le-pair
ifthere existapath p
G (x;y) anda pathP G (x;y)su h thatp G (x;y)\P G (x;y)=
fx;yg. In other words, if fx;yg is a y le-pair, then the set p
G
(x;y)[P
G (x;y)
3 Basi de nitions and preliminary results
In this se tion we formallyde ne (k;+){distan e-hereditary graphsand provide
some preliminaryresults.
De nition 3.1 Let k be a real number. A graph G is a (k;
+){distan e-hereditary graph if, for ea h onne ted indu ed subgraph G 0 of G: d G 0 (x;y)d G (x;y)+k; for ea h x;y 2G 0 : (1)
The lass of allthe (k;+){distan e-hereditary graphs is denoted by DH(k;+).
Noti e that the above de nition holds for both onne ted and dis onne ted
graphs. Given a rational number k 1, the (k;){distan e-hereditary
graphs [8,9℄ have been de ned in a similar way: it is suÆ ient to repla e Eq. 1
by the followingone:
d G 0(x; y)d G (x;y)k; for ea h x;y2G 0 : (2)
DH(k;) denotes the lass of all (k;){distan e-hereditary graphs. By setting
k = 0 in Eq. 1 or k = 1 in Eq. 2, we get the de nition of distan e-hereditary
graphs[18, 19℄.
Lemma 3.2 The lass DH(k;+)is losed under taking indu ed subgraphs.
Proof. Let G be a graph in DH(k;+) and G 0
be an indu ed subgraph of G.
A ording to De nition 3.1, we have to show that, for ea h onne ted indu ed
subgraph G 00 of G 0 , d G 00 (x;y)d G 0(x; y)+k; for ea hx;y2G 00 .
Let x and y be two nodes in G 00
. Sin e G 00
is a onne ted indu ed subgraph
of G, then, by De nition 3.1, d G 00(x;y) d G (x;y)+k. Relationship d G (x;y) d G 0(x;
y) is straightforward. Combiningthese inequalities,we get
d G 00 (x;y) d G (x;y)+k d G 0 (x;y)+k 2
De nition 3.3 Let G be a graph, and fx;yg be a pair of onne ted nodes in G.
Then:
1. the dilation number
G
(x;y) of the pair fx;yg is given by
G (x;y) = D G (x;y) d G (x;y);
2. the dilation number (G) of G is the maximum dilation number over all
possiblepairs of onne ted nodes, that is, (G)=max
fx;yg
G (x;y);
ber of G, thatis, D(G)=ffx;yg j
G
(x;y)=(G)g.
In the ontext of (k;){distan e-hereditary graphs, we introdu ed the
orre-sponding notion of stret h number. Shortly, if G is a graph and x and y two
onne ted nodes in G, then : (1) the stret h number s
G (x;y) of fx;yg is given by s G (x;y)= D G (x;y)=d G
(x;y), and (2) the stret h number s(G) of G is given
by s(G)=max
fx;yg s
G (x;y).
The following two lemmas list some basi properties of (k;
+){distan e-hereditary graphs.
Lemma 3.4 Thefollowing fa ts hold:
1. DH(0;+) oin ides with the lass of distan e-hereditary graphs;
2. DH(k;+)=DH(bk ;+), for ea h real number k 0;
3. DH(k
1
;+)DH(k
2
;+), for ea h pair of integers k
1 and k 2 , k 1 k 2 ; 4. If (x;y)2E then G (x;y)=0. As a onsequen e:
- if (G)=0 then D(G) ontains every pairs of onne ted nodes of G;
- if (G)>0 then d
G
(x;y)2 for ea h pairfx;yg2D(G);
5. if G ontains n nodes, then (G) maxf0;n 4g; moreover, for ea h
n2N there exists a graph G 0
su h that (G 0
)=n;
Proof. Fa ts 1, 2, 3, and 4 dire tly follow from De nition 3.1. The remainder
proves Fa t 5.
Ifn 4,then Gisa distan e-hereditarygraph and hen e(G)=0. Ifn >4
and G62DH(0;+), then:
a) d
G
(x;y)2,for ea h fx;yg2D(G)(see Fa t 4);
b) D
G
(x;y)n 2,for ea h pair fx;yg of onne ted nodes in G.
Then,if fx;yg2D(G), the followingholds:
(G) = D
G
(x;y) d
G
(x;y) (n 2) 2 = n 4
To omplete the proof weshow that (H
n
)=n 4, forn 4. H
4
isa
distan e-hereditary graph, and hen e (H
4
) = 0. When n > 4, for ea h pair fx;yg of
nodes in H n su h that d H n (x;y) 2,we have D H n (x;y)= n d H n (x;y). Then, H n (x;y) = D H n (x;y) d H n (x;y) = n 2d H n
(x;y), whi h is maximum for
d
Hn
(x;y)=2. Hen e (H
n
)=n 4. 2
The dilation number an be used to provide a rst hara terization of (k;+){
u 1 u 2 u 3 k +3 u k +4 v 1 v 2 v 3 k +3 v k +4
Figure2: ThegraphG
k
, k 1,used byLemma3.6. It onsistsof two holesH
k+4
joined byan edge.
Theorem 3.5 Let G be a graph. G2DH(k;+)if and only if(G)k.
Proof. We rst show that the following relationship holds:
(G)=minft:G2DH(t;+)g (3) ByDe nition 3.3, (G)=max fx;yg fD G (x;y) d G
(x;y)g,that is,
(G)D
G
(x;y) d
G (x;y)
forea hpairof onne tednodes x;y 2V. IfG 0 =(V 0 ;E 0 )isa onne tedindu ed subgraph of G, then (G) d G 0 (x;y) d G (x;y) for ea h x;y 2 V 0 . Hen e d G 0(x; y)d G (x;y)+(G)for ea h x;y2V 0 . Bythe generalityof G 0 , itfollows that G2DH((G);+).
By ontradi tion, let us suppose that there exists an integer t < (G) su h
that G 2 DH(t;+). Let fx;yg 2 D(G), and G 0
be the subgraph indu ed by
P
G
(x;y). In this ase we have that d
G
0(x;y)=D
G
(x;y),and hen e the relation
D G (x;y) d G (x;y)=(G)>t implies that d G 0 (x;y)=D G (x;y)>t+d G (x;y):
Then G 62 DH(t;+), a ontradi tion. The theorem follows by Eq. 3 and Fa t 3
of Lemma3.4. 2
In [8℄, it is shown that G2 DH(k;) if and only if s(G) k. We on lude this
se tion by providing a relationship between the lasses DH(k;+) and DH(k;),
useful inthe remainder of the paper.
Lemma 3.6 For ea h k 1, DH(k;+)DH(1+ k
2 ;).
Proof. Let G 2DH(k;+), k 1, and x;y 2G. We show that s
G
(x;y) 1+ k
2 .
By the generality of x and y, this implies G 2 DH(1 + k 2 ;), and, in turn, DH(k;+)DH(1+ k 2 ;).
v 1 v 2 v 3 v 4 v 5 v 1 1 v 1 2 v 1 3 v 2 1 v 4 v 5 v 1 5 v 1 4 v 2 3 v 2 2
Figure 3: A graph G and its twin graph G
(see De nition 4.1). Dashed lines
representedges inE 3 . Nodes v 1 1 ;v 1 2 ;:::;v 1 5 andv 2 1 ;v 2 2 ;:::;v 2 5
indu e thesubgraphs
G 1 and G 2 , respe tively. Both G 1 and G 2 are isomorphi to G. By Theorem 3.5, (G) k. Hen e, D G (x;y)d G (x;y)+k. If d G (x;y)=1, then s G (x;y) = 1 and relation s G (x;y) 1+ k 2 trivially holds. If d G (x;y) 2, then: s G (x;y)= D G (x;y) d G (x;y) d G (x;y)+k d G (x;y) =1+ k d G (x;y) 1+ k 2
To omplete the proof we show that the graph G
k
of Fig. 2 is su h that G
k 2 DH(1+ k 2 ;)and G k
62DH(k;+),for ea hk 1. Infa t,
G k (u 2 ;v 2 )=(k+2)+ 1+(k+2) 5 = 2k, while s(G k ) = s G k (u 2 ;u k+4 ) = k+2 2 = 1+ k 2 (in [8℄, it is
shown that the stret h number of a graph H oin ides with the stret h number
of one of the maximal bi onne ted omponents of H). 2
4 Chara terization of graphs in DH (k;+)
In[8℄, itisshownthatthe(k;){distan e-hereditarygraphsenjoyani e\lo ality
property": the stret h number of G oin ides with the stret h number of an
indu ed subgraph of G that forms a y le. This property does not hold for
(k;+){distan e-hereditary graphs. For instan e, onsider again the graph G
k of
Fig.2: the longestand the shortest indu ed path between every pair ofnodes in
D(G
k
) does not indu ea y le (indeed, the pairs indu e the whole G
k ).
In this se tion, we introdu e the notion of twin graph. We show that the
lo- alityproperty re alledaboveholdsfortwin graphsof (k;+){distan e-hereditary
graphs. In thisway, we areable toprovidea hara terization of(k;
+){distan e-hereditary graphs based on y le- hord onditions (Theorem 4.6).
De nition 4.1 Let G = (V;E) be a graph. The twin graph of G is a graph
G =(V ;E ) su h that V =V 1 [V 2 and E =E 1 [E 2 [E 3 , where: - V 1 =fv 1 j v 2Vg;
- V =fv j v 2Vg; - E 1 =f(u 1 ;v 1 ) j (u;v)2Eg; - E 2 =f(u 2 ;v 2 ) j (u;v)2Eg; - E 3 =f(u 1 ;v 2 );(u 2 ;v 1 ); j (u;v)2Eg. The subgraphs of G given by (V 1 ;E 1 ) and (V 2 ;E 2 ) are denoted by G 1 and G 2 , respe tively. ThenjV j=2jVjand jE
j=4jEj. The name \twin graph"isdue to thefa t
that, for ea h pair (v 1 ;v 2 ) of nodes in G su h that v 1 2 V 1 and v 2 2 V 2 , v 2 is a false twin of v 1 in G
. Hen e, the twin graph G
an be obtained from G by
applying operation (G;v)to ea h node v of G. Moreover, noti e that both G 1
and G 2
are indu ed subgraphs of G
and isomorphi to G(see Fig.3).
De nition 4.2 Let S bethe subgraphof G
indu edbythenodes v i 1 1 ;v i 2 2 ;:::;v in n , i j
2 f1;2g and 1 j n. The proje tion of S on G 1 , denoted by S 1 , is the subgraph of G 1
indu ed by the nodes v 1 1 ;v 1 2 ;:::;v 1 n .
Noti ethat, theproje tionof G 2
onG 1
orresponds toG 1
. The followinglemma
deals with proje tions of generi indu ed subgraphs of G
.
Lemma 4.3 Let S be an indu ed subgraph of G
. If there are no false twins in
S, then S and its proje tion S 1 are isomorphi . Proof. Let S = (V S ;E S ), S 1 = (V S 1;E S
1), and assume that there are no false
twins inV S =fv i 1 1 ;v i 2 2 ;:::;v i n n
g. We showthat S and S 1
are isomorphi ,that is:
(1)jV S 1j=jV S j, and (2) (v i j j ;v i k k )2E S if and only if (v 1 j ;v 1 k )2E S 1. 1. By onstru tion of V S 1, it follows that jV S 1j jV S j. A ording to De ni-tion 4.1, jV S 1
j ontains less elements than jV
S
j if and only if two di erent
nodes in V
S
have the same orresponding node in V
S
1, i.e, there exist two
distin t nodes v i j j and v i k k in V S , i j 6= i k , su h that v 1 j v 1 k . If su h two
nodes exist, by De nition 4.1, v i j j and v i k k
are false twins in G
. As a
on-sequen e, sin e S is indu ed in G then v i j j and v i k k
are false twins in S, a
ontradi tion. Hen e, jV S 1 j=jV S j.
2. The property that (v i j j ;v i k k ) 2 E S if and only if (v 1 j ;v 1 k ) 2 E S 1 dire tly
follows from de nition of G
.
2
Lemma 4.4 For k 0, G2DH(k;+) if and only if G
Proof. =): Assuming G 62 DH(k;+), there exist two nodes u;v 2 V su h that D G (u; v) d G (u; v) > k. Let P G (u;v) = (u v i 0 0 ;v i 1 1 ;:::;v i n n v), i j 2f1;2gand 0j n, and p G (u;v)=(uu `0 0 ;u `1 1 ;:::;u `m m v),` j 2f1;2g
and 0 j m, be a longest and a shortest indu ed path onne ting u and v,
respe tively. A ordingto the fa t that there are false twins inan indu ed path
if and onlyif the path has three nodes, we analyze two di erent ases:
1. m=2:
In this ase, p
G
(u;v) has three nodes. Moreover, n > 2 otherwise G
2
DH(0;+),a ontradi tionforthehypothesisG 62DH(k;+). Thesubgraph S indu ed by P G (u;v)[ p G (u;
v) is a y le with at least 5 nodes and
hord distan e atmost 1. It an be easilyobserved that su h a y le does
not ontains false twins. Then, by Lemma 4.3, the proje tion S 1
of S is
isomorphi to S.
By observing that (S) > k, it follows that (S 1 ) > k. Hen e, by Lemma 3.2, G 1 62 DH(k;+). Finally, sin e G 1 is isomorphi to G, then G62DH(k;+). 2. m>2:
In this ase, neither the subgraph indu ed by P
G (u;
v) nor the subgraph
indu ed by p
G (u;
v) has false twins. Let P 1 (v 1 0 ;v 1 n ) and p 1 (u 1 0 ;u 1 m ) be the proje tions of P G (u;v) and p G (u;v)on G 1 , respe tively. By Lemma 4.3, P 1 (v 1 0 ;v 1 n )and p 1 (u 1 0 ;u 1 m ) areisomorphi toP G (u;v)andp G (u; v), respe -tively. Sin eD G 1 (v 1 0 ;v 1 n ) d G 1 (u 1 0 ;u 1 m )jP 1 (v 1 0 ;v 1 n )j jp 1 (u 1 0 ;u 1 m )j=jP G (u; v)j jp G (u;v)j> k, then G 1 62DH(k;+). Finally,sin e G 1 is isomorphi toG, thenG62DH(k;+). (=: Assume G
2 DH(k;+). Sin e G is an indu ed subgraph of G
, then, by
Lemma3.2, G2DH(k;+). 2
Lemma 4.5 Let G be a graph su h that (G) > 0. Then, D(G
) ontains a
y le-pair of G
.
Proof. Letfx;yg2D(G). LetP
G (x;y)=(xv 0 ;v 1 ;:::;v n y)andp G (x;y)= (x u 0 ;u 1 ;:::;u m
y) be a longest and a shortest indu ed path onne ting x
and y, respe tively. Now, two ases may arise:
1. P G (x;y)\p G (x;y)=fx;yg: In this ase, P G (x;y) = (x v 1 0 ;v 1 1 ;:::;v 1 n y) and p G (x;y) = (x u 1 0 ;u 1 1 ;:::;u 1 m
y)formthe requested y le-pairinG
(rememberthat,By
Lemma4.4, (G)=(G
G G
In this ase, sele t p 0 G (v 1 0 ;v 1 n ) = (x v 1 0 ;v 2 1 ;v 2 2 :::;v 2 n 1 ;v 1 n y) and p 00 G (u 1 0 ;u 1 m ) = (x u 1 0 ;u 1 1 ;:::;u 1 m
y). To show that fx;yg 2 D(G
),
it is suÆ ient to observe that: p 0 G (v 1 0 ;v 1 n ) and p 00 G (u 1 0 ;u 1 m ) are indu ed in G , jP G (x;y)j = jp 0 G (v 1 0 ;v 1 n )j, and jp G (x;y)j = jp 00 G (u 1 0 ;u 1 m )j (by onstru -tionofG );fx;yg2D(G)(byhypothesis);(G)=(G )(byLemma4.4). 2
The following theorem provides a y le- hord hara terization for graphs in
DH(k;+), k 0.
Theorem 4.6 Let G be a graph and k 0 be an integer. Then, G 2 DH(k;+)
if and only if d(C
n )
n k
2
1for ea h y le C
n
, n >k+4, of G
.
Proof. =): Assume G 2 DH(k;+), k 0. By ontradi tion, suppose there
exists a y le C n , n > k + 4, in G su h that d(C n ) < n k 2 1. Let C n = (x;v 1 ;v 2 ;:::;v q ;y;u p ;u p 1 ;:::u 1 ), p+ q + 2 = n, and fv 1 ;v 2 ;:::;v q g
the set of nodes giving the hord distan e of C
n (hen e, d(C n ) = q). Sin e (x;v 1 ;v 2 ;:::;v q ;y) is a path in G , then d G (x;y) q + 1; moreover, sin e (x;u 1 ;u 2 ;:::u p ;y) is an indu ed path in G , then D G (x; y) p+1. It follows that: D G (x;y) d G (x;y)(p+1) (q+1) =p q =(n q 2) q =n 2q 2 >n 2( n k 2 1) 2 =k Hen e, D G (x; y) d G (x; y) > k, that is (G ) > k. This is a ontradi tion,
be ause, by Lemma 4.4, G2DH(k;+) impliesG 2DH(k;+). (=: Assume d(C n ) n k 2
1for ea h y le C
n
,n >k+4, of G
. By
on-tradi tion, suppose G 62DH(k;+). In this ase, by Lemma 4.4, G
62 DH(k;+),
andhen e (G
)>0. Now, by Lemma 4.5and Fa t 4of Lemma3.4there exists
a y le-pair fx;yg 2 D(G
) indu ing a y le C
n
with n nodes and su h that
d G (x; y)2. Sin e G 62DH(k;+), then D G (x;y)>k+d G (x; y). Moreover, n=D G (x;y)+d G (x;y) >k+d G (x;y)+d G (x; y) =k+2d G (x; y)
impliesthat d G (x;y)< 2 . Finally, sin e d(C n )=d G (x;y) 1,then d(C n )< n k 2 1; a ontradi tion. 2
5 Re ognition problem for DH (k;+)
In this se tion we study the re ognition problem for the lass DH(k;+) when k
isnot xed. We start by de ning the followingde ision problem:
De nition 5.1 Dilation Number Problem:
Instan e: A graph G=(V;E), an integer q0.
Question: (G)>q?
The NP- ompleteness of this problem an be shown by providing a polynomial
transformation from the NP- omplete problem Indu ed Path ( f. [15℄, GT23),
that an be formallyde ned asfollows:
Instan e: A graph G=(V;E),a positiveinteger k jVj.
Question: IsthereasubsetP V withjPjksu hthatthesubgraphindu ed
by P isan indu ed path onjPj nodes ?
In the following result, we use the version of Indu ed Pathin whi h 1<k
jVj. Obviously,this problemisstill NP- omplete.
Theorem 5.2 Dilation Number is NP- omplete.
Proof. Itiseasytosee thatthe DilationNumberproblembelongstoNP,asgiven
apair of paths joiningtwo nodes inV itis possible to he k inpolynomialtime
whether the di eren e of their lengthsis greaterthan q.
Given agraphG=(V;E)andapositiveintegerk representing aninstan e of
Indu edPath, inpolynomialtime we onstru t agraph G 0
and de ne aninteger
q su h that there exists the required indu ed path in G if and only if (G 0
) is
greaterthan q.
The redu tion graph G 0
= (V 0
;E 0
) is obtained as follows: for ea h node
v 2 V, add a pendant node v to v. These new nodes form the independent set
W =fv j v 2 Vg. Then, onne t all the nodes in V [W to a new node u (see
Fig.4). Formally:
- V 0
=V [W [fug;
- V;W and fugare pairwisedisjointsets with jWj=jVj;
- E 0
. . . . . . v W V v
Figure4: The graph G 0
built using the instan e G= (V;E) of the Indu ed Path
problem. W is an independent set ontaining a node v for ea h node v 2V.
Con erningthe rationalnumber q, itis given by q =k 2.
Now weprovethat the instan e of Indu edPath has a positiveanswerif and
onlyif (G 0
)>q.
=): Assume that the instan e of Indu ed Path has a positive answer. This
impliesthat anindu ed path p=(v
1 ;v
2 ;:::;v
n
)exists inhVi su h that jpj k.
Thenthepathp=(v
1 ;v 1 ;:::;v n ;v n
)isalsoanindu edpathinG 0 andjpjk+2. Byde nitionofG 0 ,nodesv 1 and v n
are notadja ent,andsin ethey are both
adja ent tou, then d G 0 (v 1 ;v n
)=2. Hen e, the following relationholds:
(G 0 ) D G 0 (v 1 ;v n ) d G 0 (v 1 ;v n ) (k+1) 2 = k 1 > q
This impliesthat the instan e of Stret h Number has a positive answer.
(=: Let us assume that Dilation Number has a positive answer, that is
(G 0
)>q. By de nition of dilationnumber there existtwonodes x;y 2G 0
su h
that
G 0
(x;y) > q. Nodes x and y annot be adja ent otherwise
G 0
(x;y) = 0
(a ontradi tion for (G 0
) > q 0). For the same reason, neither x nor y an
oin ide with u, being u adja ent to ea h other node in G 0
. Then, d
G 0
(x;y) =
2. This implies that the relation D
G 0 (x;y) d G 0 (x;y) > q an be rewritten as D G 0 (x;y)>q+2. Then, D G 0 (x;y) > q+2 = (k 2)+2 = k Letp=(x;v 1 ;:::;v n
;y)beanindu edpath between x andy whoselengthis
equal to D
G
0(x;y). If p ontains u, then P
G
G i
V [W. Moreover, sin e p does not ontain u and sin e the elements of W are
pendant nodes in hV [Wi,then v
i
62W, 1in.
Now, three di erent ases arise, a ording to the membership of x and y to
W. Noti e that jpj>k+1 be ause jpj=D
G 0
(x;y)+1>k+1.
1. Both x and y are in V. In this ase p is an indu ed path in G, and sin e
jpj>k+1, then p itself is a solution for the instan e of the Indu ed Path
problem.
2. x2V and y2W. In this ase p 0 =(x;v 1 ;:::;v n )is anindu ed pathinG,
and sin e jpj >k+1, then jp 0
j >k and p 0
is a solutionfor the instan e of
the Indu ed Path problem.
3. Bothxand yare inW. Inthis ase p 00 =(v 1 ;:::;v n )isanindu ed path in
G,and sin e jpj>k+1, thenjp 00
jk and p 00
is asolutionfor the instan e
of the Indu ed Path problem.
This impliesthat the instan e of Indu ed Pathhas a positive answer. 2
Ifwe xk =0,thenthere ognitionproblemforthe lassDH(k;+) anbesolved
in linear time [19℄. If we onsider k not xed, then the re ognition problem for
the lass DH(k;+) is exa tly the omplementary problem of Dilation Number.
As a onsequen e, the following omplexity result an be stated.
Corollary 5.3 If k is not xed, the re ognition problem for the lass DH(k;+)
is Co-NP- omplete.
6 Chara terization of graphs in DH (1;+)
Inthis se tionweprovidea hara terization forthe smallest lassamongthenew
ones, i.e., lass ontaining (1;+){distan e-hereditary graphs. Theorem 6.6 lists
allthe forbidden indu ed subgraphs of every graphin DH(1;+).
Lemma 6.1 Let Gbe agraph ontaining, as indu edsubgraphs,a y le C
n with
n 6 and d(C
n
) 1. Then, G ontains one of the y les of Fig. 5 as indu ed
subgraphs, thatis:
1. H n , for ea h n6; 2. y les C 6 with d(C 6 )=1; 3. y les C 7 with d(C 7 )=1; 4. y les C 8 with d(C 8 )=1.
hord must exist. The dotted line represents a path; a dashed line represents an
edge that may or may not exist.
Proof. LetC
n
be the y le ontained, asindu ed subgraphs, inG:
1. n6and d(C
n )=0:
In this ase the statement is triviallytrue (sin e G ontains H
n , n 6, as indu ed subgraph); 2. 6n 8and d(C n )=1:
Alsointhis ase thestatementis triviallytrue (sin eG ontains oneof the
y les of Fig. 5having hord distan e 1,as indu ed subgraph);
3. n9and d(C n )=1: LetC n =(u 1 ;u 2 ;:::;u n
), and assumethat allthe hords of C are in ident
tou
1
. Denote by l the smallest index j su h that u
j
and u
1
are onne ted
by a hord of C, i.e. l = minfj j (u
j ;u 1 ) isa hord of Cg. If l 6, then the y le(u 1 ;u 2 ;:::;u l
)isaholewithatleast6nodes,andthenthelemma
holds. Ifl <6,then the y le (u
1 ;u l ;u l +1 ;:::;u n ) ontains n 0 n 36
nodes and has hord distan e at most 1. Now, if the latter y le is one of
the y les ofFig. 5weare done, otherwise we an re ursivelyapply tothis
y le the arguments above.
The analysis of these three ases on ludes the proof. 2
Lemma 6.2 Let G be a graph and let G
its twin graph. G 2 DH(1;+) if and
only if the followinggraphs are not indu ed subgraphs of G : 1. H n , for ea h n6; 2. y les C 6 with d(C 6 )=1; 3. y les C 7 with d(C 7 )=1; 4. y les C 8 with d(C 8 )=1; 5. y les C 2i+4 with d(C 2i+4 )=i, for ea h i2.
n
7, or 8 nodes and hord distan e 1 have dilation number equal to 2, 3, and 4,
respe tively. Cy les C
2i+4
with horddistan e equaltoihave dilationnumberat
least2i+4 2( d(C
2i+4
)+1)=2. Then,they areforbiddenindu ed subgraphs
forG and, by Lemma4.4, also forG
.
(=: AssumingG62DH(1;+),weshowthatG
ontains oneoftheforbidden
subgraphs. IfG62DH(1;+)then,byTheorem4.6,G
ontainsa y le C
n
,n 6,
asindu ed subgraph su hthat 0 d(C
n )<
n 3
2
. In what follows weshow that
eitherC
n
ontains oneofthe y les inthe statementofthe lemmaorC
n ontains a y le C n 0 62 DH(1;+) as indu ed subgraph, n 0
< n. In the latter ase we an
re ursively apply to C
n
0 this proof.
Letting q 0 and n maxf6;2q +4g, onsider the y le C
n
with hord
distan e q. The analysis of C
n
is performed by ases:
1. 0q 1and n maxf6;2q+4g=6:
In this ase, by Lemma 6.1, C
n
ontains one of the y les of Fig. 5 as
indu ed subgraph.
2. q2 and n=maxf6;2q+4g=2q+4:
Inthis ase, C
n
orresponds tothe last y le in statementof the lemma.
3. q2 and n>maxf6;2q+4g=2q+4:
In this ase, assume that the y le C
n
is indu ed by the nodes of the
two node-disjoint paths P
G (x;y) = (x;u 1 ;u 2 ;:::;u p ;y) and p G (x;y) = (x;v 1 ;v 2 ;:::;v q
;y), p + q + 2 = n, su h that nodes v
1 ;v 2 ;:::;v q give
the hord distan e of C
n
. In this y le, we denote by r
j
the largest
in-dex j 0 su h that v j and u j
0 are onne ted by a hord of C
n , i.e. r j = maxfj 0 j (v j ;u j 0 )is a hord of C n g; weassume r j unde ned when v j is not in identtoa hord ofC n . Informally,r j
gives the rightmost hord in ident
tov
j
. Noti e that, sin e q1, r
1
isde ned.
Ifr
1
>3then the subgraph of C
n
indu ed by the nodes v
1 ;x;u 1 ;:::;u r 1 is
a y le with at least 6 nodes and hord distan e at most 1. A ording to
Lemma 6.1, this subgraph ontains one of the y les of Fig. 5 as indu ed
subgraph. Assume r 1 3 and let C n 0 be the subgraph of C n
indu ed by the nodes
v 1 ;v 2 ;:::;v q ;y;u p ;u p 1 ;:::;u r 1 (informally, C n
0 is one of the two y les
obtained by \ utting" C n by means of hord (v 1 ;u r1 )). Cy le C n 0 has n 0 n 36nodes (be auser 1
3) and hord distan e atmost q 1.
A ording to Theorem 4.6, by proving d(C
n 0 ) < n 0 3 2 we get C n 0 62 DH(1;+). Sin e d(C n 0) q 1, d(C n 0) < n 0 3 2
holds when the following
v 2 v 3 v 1 v k u 3 u 2 4 u 1 2 w 3 w 4 w 5
Figure6: The lepsydra graph l(k) (see De nition 6.3). The dashed edges may
or may not exist.
n 0 3 2 >q 1; (n 3) 3 2 >q 1; n>2q+4: (4)
Sin e n > 2q+4 holds by hypothesis, then d(C
n 0 ) < n 0 3 2 . This means thatC n 0
62DH(1;+), and hen e we an re ursivelyapply toC
n 0
this proof.
The analysis of the ases above on ludes the proof. 2
The following de nition introdu es the notion of lepsydra graph (see Fig. 6),
useful to hara terizegraphs in DH(1;+).
De nition 6.3 Let C 5 = (u 1 ;u 2 ;u 3 ;u 4 ;u 5
) be a y le su h that d(C
5 ) 1 and deg C 5 (u 5 ) = 2, P k = (v 1 ;v 2 ;:::;v k
) be a path with k 1, and C 0 5 = (w 1 ;w 2 ;w 3 ;w 4 ;w 5
) be a y le su h that d(C 0 5 ) 1 and deg C 0 5 (w 1 ) = 2. A
lep-sydra of order k is a graph l(k)=(V;E) su h that:
- V =fu 1 ;u 2 ;u 3 ;u 4 ;v 1 ;v 2 ;:::;v k ;w 2 ;w 3 ;w 4 ;w 5 g;
- if x;y 2 V then (x;y) 2 E if and only if one of the following ondition
holds: 1. (x;y)2f(u 1 ;v 1 );(u 4 ;v 1 );(v k ;w 2 );(v k ;w 5 )g
2. x and y are adja ent in C
5 , P k , or C 0 5 Lemma 6.4 Let G 2 DH( 3 2 ;) ontaining a y le C n
as indu ed subgraph su h
thatn 4+2i, i1, and d(C
n
)i. Then, G ontains a lepsydra as indu ed
v 0 v 1 v q 1 v 2 v q u 1 u 2 u 3 p 2 u p 1 u p v q+1
Figure 7: The y le C
n
onsidered in Lemma 6.4. Dashed edges represent
hords that may or may not exist. Nodes in y les (u
2 ;u 1 ;v 0 ;v 1 ;v 2 ) and (v q 1 ;v q ;v q+1 ;u p ;u p 1
), alongwith nodes inpath(v
3 ;v 4 ;:::;v q 2 ), indu e a
lep-sydra l(k), k 1 (k =1 when q =3), as subgraph of C
n . Proof. Let C n = (v 0 ;v 1 ;v 2 ;:::;v q ;v q+1 ;u p ;u p 1 ;:::;u 1 ) and let (v 1 ;v 2 ;:::;v q )
be the nodes giving the hord distan e of C
n
(see Figure 7). Without loss of
generality, we assume that C
n
is a y le in G that satis es the hypotheses and
has the minimum number of nodes.
We rst show that a hord onne ting two nodes in fv
0 ;v 1 ;:::;v q+1 g does not existin C n
. This isdone by analyzing three ases:
Consider a hord onne ting two nodes in fv
0 ;v 1 ;:::;v q g. Su h a hord an be denoted by (v j ;v j+t+1
), where j and t are integers su h that j
0, t 1, and j +t +1 q. Chord (v
j ;v
j+t+1
) forms the y le C
m = (v 0 ;v 1 ;:::;v j ;v j+t+1 ;:::v q+1 ;u p ;u p 1 ;:::;u 1 ). It follows that C m has m =
n t nodes and hord distan e d(C
m
)q t. Sin e
m=n t 4+2i t4+2q t4+2q 2t=4+2(q t)
and q t 1, then C
m
is a y le whi h ful lls the hypotheses as in the
statement but with less nodes than C
n
. This ontradi tsthe minimalityof
C
n .
Consider a hord onne ting two nodes in fv
1 ;v 2 :::;v q+1 g. This ase is
symmetri tothe previous one.
Chord(v
0 ;v
q+1
) doesnot exist by de nition of hord distan e.
Then, every hord (x;y) of C
n is su h that x 2 fv 1 ;v 2 ;:::;v q g (by de nition of
hord distan e) and y 2fu
1 ;u 2 ;:::;u p g.
n=p+q+24+2i and qi, and hen e: p 2i+2 q 2i+2 i = i+2: Paths (v 0 ;v 1 ;:::;v q+1 ) and (v 0 ;u 1 ;u 2 :::;u p ;v q+1
) an be used to get a lower
bound for the stret h number s
G (v
0 ;v
q+1
) (the on ept of stret h number is
re- alledafter De nition 3.3):
s G (v 0 ;v q+1 ) p+1 q+1 : (5) Moreover, sin e G2DH( 3 2
;),the followingupper bound holds:
s G (v 0 ;v q+1 ) 3 2 : (6)
And, by using q iand pi+2:
p+1 q+1 i+3 i+1 = 1+ 2 i+1 : (7)
Hen e, by ombiningEqs. 5, 6and 7,we get:
1+ 2 i+1 3 2
. This inequality an berewritten as i3;
by using pi+2 and i3we get p5;
p+1 q+1 3 2
. This inequality an be rewritten as q 2p 1
3
. By using p5 we
obtainthe requested lower bound q3.
Now we introdu e some notation about hords. For1 j q, we denote by v
l
j
andv
r
j
the nodesin ident tothe leftmostand rightmost hordof v
j ,respe tively. Formally, l j =minfj 0 j 1j 0 pand (v j ;u j 0 ) isa hord of C n g; r j =maxfj 0 j 1j 0 pand (v j ;u j 0 ) isa hord of C n g: We assume l j and r j unde ned when v j
is not in ident to a hord of C
n . By
de nition of hord distan e, l
1 , r 1 , l q , and r q are de ned.
Now we provide a formula to ompute l
j
and r
j
. Assuming l
j
de ned for some
j su h that 1 < j q, let C
n 0 and C n 00 be the subgraphs of C n indu ed by thenodesv 0 ;v 1 ;v 2 ;:::;v j ;u l j ;u l j 1 ;:::;u 1 andv j ;v j+1 ;:::;v q+1 ;u p ;u p 1 ;:::;u l j , respe tively. Informally,C n 0 and C n
00 are the y les obtained by\ utting" C
n by
meansof hord(v j ;u l j ). Sin e y le C n 0 has n =l j
+j+1 nodes,then y le C
n 00 has n 00 =n n 0 +2 4+2i (l j +j+1)+2 =2i+5 l j j
nodes. Moreover,it anbeobserved that d(C
n 0) j 1and d(C n 00 )q j+1. Wenowassumen 0 <4+2(j 1),otherwisen 0 4+2(j 1)and d(C n 0)j 1 implythat C n 0
represent a ontradi tion to the minimality ofC
n . By symmetry, we assume n 00 < 4+2(q j+1). Inequality n 0 <4+2(j 1) an be rewritten as l j +j +1 < 4+2(j 1), from whi h l j < j +1 and hen e l j j follows. Similarly,fromn 00 2i+5 l j j and n 00 <4+2(q j +1) we get: 2i+5 l j j <4+2(q j+1); l j >2(i q)+j 1; l j 2(i q)+j: Relationsl j j and l j
2(i q)+j imply the following equation:
l j =j; 1<j q: (8) Symmetri ally, r q j =p j; 1j <q: (9)
Now we show that v
2 is in ident to a hord of C n . In fa t, if v 2 is not
in- ident to a hord, let k = minfj > 2 j l
j
is de ned g. Sin e l
q
is de ned,
then 3 k q. Now, let C
n 000
be the subgraphs of C
n
indu ed by the nodes
v 0 ;v 1 ;:::;v k ;u l k ;u l k 1 ;:::;u 1 . Sin e l k
= k and k 3, then y le C
n 000 has
n 000
= 2k+1 7 nodes and hord distan e equal to 1 (in C
n 000,
only v
1
may be
in identto hords). Sin e s(C
n 000) > 3 2 ,this ontradi ts C n 2DH( 3 2 ;). As a onsequen e, l 2
must be de ned and, a ording toEq. 8,l
2 =2. Chord (v 2 ;u 2
) ontributestoformthe y leC 0 5 =(u 2 ;u 1 ;v 0 ;v 1 ;v 2
)having horddistan e
atmost 1 (see Figure7).
Symmetri ally, the same arguments an be used to show that r
q 1
is de ned
and, a ording to Eq. 9, r
q 1 = p 1. Hen e, hord (v q 1 ;u rq 1 ) ontributes
to form the y le C 00 5 =(v q 1 ;v q ;v q+1 ;u p ;u p 1
) having hord distan e at most 1
(possibly,with hords in identto v
q ). Now, y les C 0 5 and C 00 5
along with path (v
2 ;v
3 ;:::;v
q 1
) form the requested
lepsydra. Noti e that, sin e q 3, path (v
2 ;v 3 ;:::;v q 1 ) may onsists of a
singlenode (namely,v
2
). In this ase y les C 0 5 and C 00 5 share v 2
and they forma
lepsydraof order 1.
To on lude the proof we have to show that the onstru ted lepsydra is
in-deed an indu ed subgraph, that is, we have to show that nodes in C 0 5 , C 00 5 , and
2 3 q 1
Remember that, a ording to de nition of hord distan e, if su h an additional
edge exists, then it is in ident to a node in fv
1 ;v 2 ;:::;v q g. For sake of
onve-nien e,letusdenotebyX theset ontainingnodesinC 0 5 ,C 00 5 ,andv 3 ;v 4 ;:::;v q 2 . Nodes v 1 ;v 2 ;:::;v q
are analyzed by ases:
Nodes v 3 ;v 4 ;:::;v q 2 .
Assume that a node v
k
, 3 k q 2 is in ident to a hord of C
n . In
this ase, by applying Eqs. 8 and 9 we get l
k = k and r k = r q (q k) = p (q k)=p q+k. Sin e 3 k q 2, then l k 3 and r k p 2.
By analyzing indexes of nodes in y les C 0
5
and C 00
5
, it follows that hords
of v
k
annot be in ident tonodes inXnfv
k g. Node v 2 (symmetri ally,node v q 1 ).
We already know that v
2
is in ident to a hord; Eqs. 8 and 9 imply l
2 =2
and r
2
=p q+2.
Now, if q = 3, then y les C 0 4 and C 00 5 share node v 2 . Sin e l 2 = 2 and r 2
=p 1, the leftmost and the rightmost hord of v
2 ontribute to form the y les C 0 5 and C 00 5
, respe tively, while the other hords of v
2
(if any)
annotbe in ident tonodes inXnfv
2 g. If q 4, then l 2 = 2 and r 2
= p q +2 < p 1; the leftmost hord of
v
2
ontributes to form the y le C 0
5
, while the other hords of v
2
(if any)
annotbe in ident tonodes inXnfv
2 g. Node v 1 (symmetri ally,node v q ). If v 1 is in ident to a hord of C n , then, by Eq. 9, r 1 = p q+1. Sin e q 3, then r 1
= p q+1 < p 1. This implies that hords from v
1 to
othernodes of X (if any) maybein identto u
1
orto u
2 only.
This on ludes the proof. 2
In[8℄,theauthorsprovidedthe following hara terizationforgraphsinDH( 3
2 ;):
Theorem 6.5 [8℄ Let G be a graph. G 2 DH( 3
2
;) if and only if the following
graphs are not indu ed subgraphs of G:
1. H n , for ea h n6; 2. y les C 6 with d(C 6 )=1; 3. y les C 7 with d(C 7 )=1; 4. y les C 8 with d(C 8 )=1 or d(C 8 )=2.
du ethefollowing orollary. ThisresultstatesthateverygraphinDH( 3
2
;)either
belongs toDH(1;+) or ontains a lepsydra as indu ed subgraph.
Theorem 6.6 Let G be a graph. G 2 DH(1;+) if and only if the following
graphs are not indu ed subgraphs of G:
1. H n , for ea h n6; 2. y les C 6 with d(C 6 )=1; 3. y les C 7 with d(C 7 )=1; 4. y les C 8 with d(C 8 )=1 or d(C 8 )=2; 5. lepsydrae. Proof. =): Holes H n
, n 6, have dilation number at least 2. Cy les with
6, 7, or 8 nodes and hord distan e 1 have dilation number equal to 2, 3, and
4, respe tively. Cy les with 8 nodes and hord distan e 2 have dilation number
equalto2. Finally, lepsydrae have dilationnumberequalto 2.
(=: By Theorem 6.5, G 2 DH( 3
2
;). Moreover, sin e G does not ontain
lepsydrae, Lemma 6.4 implies that G does not ontain a y le C
n
, n 4+2i
and i 1, having hord distan e d(C
n
) i. Trivially, G does not ontain a
y le C
2i+4
, i 2, having hord distan e d(C
2i+4
) = i. Sin e G is an indu ed
subgraph of G
,Lemma 6.2implies that G2DH(1;+). 2
7 Re ognition problem for DH (1;+)
Theorem 6.6 provides a basis to devi e a polynomial time algorithm for the
re ognition of graphs in DH(1;+). By Lemma 3.6, we know that DH(1;+)
DH( 3
2
;);moreover, omparingthe hara terization of( 3
2
;){distan e-hereditary
graphsand(1;+){distan e-hereditarygraphsprovided by Theorems6.5and 6.6,
respe tively,itfollowsthatagraphGbelongstoDH(1;+)ifandonlyifitbelongs
to DH( 3
2
;) and does not ontain a lepsydra as indu ed subgraph. In [9℄, it is
shown that the re ognition problem for graphs in DH( 3
2
;) an be solved in
polynomial time; as a onsequen e, for our purposes it is suÆ ient to devise a
polynomialtimealgorithmto he k whether G ontains a lepsydra l(k),k 1,
asindu ed subgraph.
Che king whether G ontains a lepsydra l(k), k 2, an be performed by
analyzing every indu ed subgraph with 9 ( ase l(1)) or 10 ( ase l(2)) nodes.
Require: A graph G
Ensure: YES, i a l(k), k>2,exists asindu ed subgraph of G
1: for all AC 0 5 , B C 00 5
distin t indu ed subgraphs of G do
2: if d(A)1, d(B)1, and hA[Bi is not onne ted then
3: for all x2A, y2B su h that deg
A (x)=deg B (y)=2 do 4: G xy
:=G fN[(A x)[(B y)℄nfx;ygg
5: if x and y are onne ted inG
xy then 6: returnYES 7: end if 8: endfor 9: end if 10: end for 11: return NO
Algorithm7.1 onsiders allthe possible pairs ofdistin t y les Aand B with
5nodesthat areindu ed subgraphsof G. IfA[B indu esa onne tedsubgraph
S, then either S isnot a lepsydra orS is a lepsydra l(k)with k 2.
If d(A) 1, d(B) 1, and S is not onne ted (Line 2), then A and B
ould belong to a lepsydra. To he k this, the algorithm properly sele ts two
nodes x and y, ea h one in a di erent y le (Line 3), and it tries to nd a path
P onne ting them. P is looked for in the subgraph G
xy
obtained by removing
fromG all the nodes in A[B and their neighborsbut x and y. Then, if x and
y remain onne ted in G
xy
, this means that the sear hed path P exists.
Sin e it an be easilyobserved that Algorithm7.1 worksin polynomialtime,
then we an state the followingtheorem:
Theorem 7.1 The re ognition problem for the lass DH(1;+) an be solved in
polynomial time.
Noti e that the previous result has only a theoreti al value, sin e the provided
algorithmis not eÆ ient. In fa t, it is enough to observe that the y le at Line
1is exe uted O(n 10
) times.
8 Con lusions and open problems
In this paper we have introdu ed, hara terized, and provided algorithmi
re-sults for (k;+){distan e-hereditary graphs, a parametri extension of the lass
ofdistan e-hereditary graphs. Thesegraphs anmodel ommuni ationnetworks
having desirable onne tivity properties. In spite of the results provided in this
polynomialtimeforDH(1;+)(Theorem7.1), anditisCo-NP- ompletefor
the generi ase (Corollary5.3). What is the omputational omplexity of
there ognitionproblemfork >1, k xed? Ifsu haproblemishard,what
is the largest onstant k su h that the re ognition problem for DH(k;+)
an besolved in polynomialtime?
2. Can hara terization of graphs in DH(1;+) provided by Theorem 6.6 be
extended to other lasses DH(k;+), k>1?
3. In[7℄, optimal ompa troutings hemesare de nedforgraphsinDH(0;+).
Is itpossible tode ne ompa t routings hemes (or other kindsof routing
s hemes)for networks based ongraphs inDH(k;+), k >0?
4. Several ombinatorial problems are solvable in polynomial time for
DH(0;+). Can some of these resultsbeextended to DH(k;+), k >0?
During the revision pro ess of this paper we were informed about two related
papers. Paper [1℄ independently studies and hara terizes DH(1;+); its main
result is a statement whi h is equivalent to Theorem 6.6. Paper [22℄, starting
fromthe preliminaryversion of this work [5℄, extends results provided by
Theo-rems6.6 and 7.1tothe ase k=2. Hen e, paper[22℄providespartialanswers to
questions1 and 2 above.
Amore hallenging problemistostudythe (s;d){distan e-hereditarygraphs,
i.e, graphs obtained by omposing the notions of (s;){distan e-hereditary and
(d;+){distan e-hereditarygraphs. Thesegraphsformthe lassDH(s;d),and an
be formallyde ned as follows: Let s 1 and d 0 be a rational and a natural
number, respe tively. A graph Gis a(s;d){distan e-hereditary graph if, for ea h
onne ted indu ed subgraph G 0 of G: d G 0 (x;y)sd G (x;y)+d; for ea h x;y2G 0 :
A knowledgments Wethanktheanonymousrefereesfortheir arefulreading
and many useful detailed ommentswhi h lead toa numberof improvements to
the presentation of the paper.
Referen es
[1℄ Meziane Ader. Almost distan e-hereditary graphs. Dis rete Mathemati s,
242:1{16, 2002.
[2℄ H.J.Bandelt andM. Mulder. Distan e-hereditarygraphs. Journal of
MonographsonDis rete Mathemati sandAppli ations,Philadelphia,1999.
[4℄ J.Bru k, R.Cypher,andC.-T.Ho. Fault-tolerantmesheswithsmalldegree.
SIAM J. on Computing, 26(6):1764{1784, 1997.
[5℄ S. Ci erone, G. D'Ermiliis, and G. Di Stefano. (k;+){distan e-hereditary
graphs(extendedabstra t).InPro .27thInternationalWorkshopon
Graph-Theoreti Con epts in Computer S ien e, WG2001, pages 66{77. Le ture
Notes in ComputerS ien e, vol. 2204, Springer-Verlag,2001.
[6℄ S.Ci erone and G. DiStefano. Graph lasses between parity and
distan e-hereditary graphs. Dis rete AppliedMathemati s, 95(1-3): 197{216,August
1999.
[7℄ S. Ci erone, G. DiStefano, and M. Flammini Compa t-Port routing
mod-els and appli ations to distan e-hereditary graphs. Journal of Parallel and
Distributed Computing, 61: 1472{1488, O tober 2001.
[8℄ S. Ci erone and G. Di Stefano. Graphs with bounded indu ed distan e.
Dis rete Applied Mathemati s, 108(1-2): 3{21, January2001.
[9℄ S. Ci erone and G. Di Stefano. Networks with small stret h number. In
Pro . 26th International Workshop on Graph-Theoreti Con epts in
Com-puter S ien e, WG2000,pages 95{106. Le tureNotes in Computer S ien e,
vol.1928,Springer-Verlag,2000.FullpapertoappearonJournalof Dis rete
Algorithms.
[10℄ S. Ci erone, G. Di Stefano, and D. Handke. Survivable networks with
bounded delay: The edge failure ase (Extended Abstra t). In Pro . 10th
AnnualInternational Symp.AlgorithmsandComputation,ISAAC'99,pages
205{214. Le ture Notes in Computer S ien e, vol. 1741, Springer-Verlag,
1999.
[11℄ G. D'Ermiliis. Topologie di reti on parti olari aratteristi he metri he (in
Italian). Master thesis,Fa ultyof Engineering,University ofL'Aquila,June
2000.
[12℄ G.DiStefano.Aroutingalgorithmfornetworksbasedondistan e-hereditary
topologies. In 3rd Int. Colloquium on Stru tural Information and
Commu-ni ation Complexity (SIROCCO'96),1996.
[13℄ A. H. Esfahanian and O. R. Oellermann. Distan e-hereditary graphs and
multidestination message-routing in multi omputers. Journal of Comb.
essing Letters, 3(4):381{391,1993.
[15℄ M.R. Garey and D.S. Johnson. Computers and Intra tability. A Guide to
the Theory of NP- ompleteness. W.H. Freeman, 1979.
[16℄ J. P. Hayes. A graph model for fault-tolerant omputing systems. IEEE
Transa tions on Computers,C-25(9):875{884, 1976.
[17℄ F. Harary. Graph Theory. Addison-Wesley, 1969.
[18℄ E.Howorka. Distan ehereditarygraphs.Quart. J.Math.Oxford,2(28):417{
420, 1977.
[19℄ P.L.HammerandF.Ma ray.Completelyseparablegraphs.Dis reteApplied
Mathemati s, 27:85{99, 1990.
[20℄ F. T. Leighton, B. M. Maggs, and R. K. Sitaraman. On the fault
toler-an e of some popular bounded-degree networks. SIAM J. on Computing,
27(6):1303{1333,1998.
[21℄ D.Pelegand A.S ha er. Graphspanners. Journal of Graph Theory,13:99{
116, 1989.
[22℄ D. Rautenba h. Graphs with small additive stret h number. Submitted
