document: in this paper , @xmath1 will be a simple graph with vertex set @xmath2 and edge set @xmath3 . 
   [ closeddef ] a _ labeling _ of @xmath1 is a bijection @xmath4 = \{1,\dots , n\}$ ] , and given a labeling , we typically assume @xmath5 $ ] . 
   a labeling is _ closed _ if whenever we have distinct edges @xmath6 with either @xmath7 or @xmath8 , then @xmath9 . 
   finally , a graph is _ closed _ if it has a closed labeling . 
   a labeling of @xmath1 gives a direction to each edge @xmath10 where the arrow points from @xmath11 to @xmath12 when @xmath13 , i.e. , the arrow points to the bigger label . 
   the following picture illustrates what it means for a labeling to be closed : @xmath14 ( n1 )   at ( 2,1 ) { $ i\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n2 )   at ( 1,3 )   { $ \rule[-2.5pt]{0pt}{10pt}j$ } ;    \node[vertex ] ( n3 ) at ( 3,3 ) { $ k\rule[-2.5pt]{0pt}{10pt}$ } ;      \foreach \from/\to in { n1/n2,n1/n3 } \draw[- > ] ( \from)--(\to ) ; ;     \foreach \from/\to in { n2/n3 } \draw[dotted ] ( \from)--(\to ) ; ;    \end{tikzpicture}&\hspace{30pt } & \begin{tikzpicture }    \node[vertex ] ( n1 )   at ( 2,1 ) { $ i\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n2 )   at ( 1,3 )   { $ j\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n3 ) at ( 3,3 ) { $ k\rule[-2.5pt]{0pt}{10pt}$ } ;      \foreach \from/\to in { n2/n1,n3/n1 } \draw[- > ] ( \from)--(\to ) ; ;     \foreach \from/\to in { n2/n3 } \draw[dotted ] ( \from)--(\to ) ; ;    \end{tikzpicture } \end{array}\ ] ] whenever the arrows point away from @xmath11 ( as on the left ) or towards @xmath11 ( as on the right ) , closed means that @xmath12 and @xmath15 are connected by an edge . 
   closed graphs were first encountered in the study of binomial edge ideals . 
   the _ binomial edge ideal _ of a labeled graph @xmath1 is the ideal @xmath16 in the polynomial ring @xmath17 $ ] ( @xmath18 a field ) generated by the binomials @xmath19 for all @xmath20 such that @xmath10 and @xmath13 . 
   a key result , discovered independently in @xcite and @xcite , is that the above binomials form a grbner basis of @xmath16 for lex order with @xmath21 if and only if the labeling is closed . 
   the name `` closed '' was introduced in @xcite . 
   binomial edge ideals are explored in @xcite and @xcite , and a generalization is studied in @xcite . 
   the paper @xcite characterizes closed graphs using the clique complex of @xmath1 , and closed graphs also appear in @xcite .    the goal of this paper is to characterize when a graph @xmath1 has a closed labeling in terms of properties that can be seen directly from the graph . 
   our starting point is the following result proved in @xcite . 
   [ hprop ] every closed graph is chordal and claw - free . 
   `` claw - free '' means that @xmath1 has no induced subgraph of the form @xmath22 ( k ) at ( 3,6 ) { $ \bullet$ } ;    \node[vertex ] ( j )   at ( 2.1,3.9){$\bullet$ } ;    \node[vertex ] ( l ) at ( 3.9,3.9 ) { $ \bullet$ } ;     \node[vertex ] ( i ) at ( 3,5){$\bullet$ } ;      \foreach \from/\to in { 
   i / l , i / k , i / j }      \draw ( \from ) -- ( \to ) ;    \end{tikzpicture } \end{array}\ ] ]    besides being chordal and claw - free , closed graphs also have a property called _ narrow_. the _ distance _ @xmath23 between vertices @xmath24 of a connected graph @xmath1 is the length of the shortest path connecting them , and the _ diameter _ of @xmath1 is @xmath25 . given vertices @xmath24 of @xmath1 satisfying @xmath26 , a shortest path connecting @xmath27 and @xmath28 
   is called a _ longest shortest path _ of @xmath1 . 
   [ narrowdef ] a connected graph @xmath1 is _ narrow _ if for every @xmath29 and every longest shortest path @xmath30 of @xmath1 , either @xmath31 or @xmath32 for some @xmath33 . 
   thus a connected graph is narrow if every vertex is distance at most one from every longest shortest path . 
   here is a graph that is chordal and claw - free but not narrow : @xmath34 ( n1 )   at ( 3,1 ) { $ a\rule[-2pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n2 )   at ( 2,3 )   { $ b\rule[-2pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n3 ) at ( 4,3 ) { $ c\rule[-2pt]{0pt}{10pt}$ } ;      \node[vertex ] ( n4 ) at ( 3,5){$e\rule[-2pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n5 ) at ( 5,5){$f\rule[-2pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n6 ) at ( 1,5){$d\rule[-2pt]{0pt}{10pt}$ } ;      \foreach \from/\to in { n1/n2,n1/n3,n2/n3,n2/n4 , n3/n4 , n3/n5 ,      n4/n5,n2/n6,n4/n6 }   \draw ( \from)--(\to ) ; ;    \end{tikzpicture } \end{array}\ ] ] narrowness fails because @xmath35 is distance two from the longest shortest path @xmath36 . 
   we can now state the main result of this paper . 
   [ mainthm ] a connected graph is closed if and only if it is chordal , claw - free , and narrow . 
   this theorem is cited in @xcite . since 
   a graph is closed if and only if its connected components are closed @xcite , we get the following corollary of theorem  [ mainthm ] . 
   [ cormainthm ] a graph is closed if and only if it is chordal , claw - free , and its connected components are narrow . 
   the independence of the three conditions ( chordal , claw - free , narrow ) is easy to see . 
   the graph is chordal and narrow but not claw - free , and the graph is chordal and claw - free but not narrow . finally , the @xmath37-cycle @xmath38 ( a )   at ( 2,1 ) { $ \bullet$ } ;    \node[vertex ] ( b )   at ( 4,1 )   { $ \bullet$ } ;    \node[vertex ] ( c ) at ( 4,3 ) { $ \bullet$ } ;      \node[vertex ] ( d ) at ( 2,3 ) { $ \bullet$ } ;      \foreach \from/\to in { a / b , b / c , c / d , d / a } \draw ( \from)--(\to ) ; ;    \end{tikzpicture}\ ] ] is claw - free and narrow but not chordal . 
   the paper is organized as follows . in section  [ properties ] 
   we recall some known properties of closed graphs and prove some new ones , and in section  [ algorithm ] we introduce an algorithm for labeling connected graphs . 
   section  [ characterize ] uses the algorithm to prove theorem  [ mainthm ] .    in a subsequent paper @xcite we will explore further properties of closed graphs . 
   a path in a graph @xmath1 is @xmath39 where @xmath40 for @xmath41 . 
   a single vertex is regarded as a path of length zero . 
   when @xmath1 is labeled , we assume as usual that @xmath42 $ ] 
   . then a path @xmath43 is _ directed _ if either @xmath44 for all @xmath12 or @xmath45 for all @xmath12 . here is a result from @xcite . 
   [ directed ] a labeling on a graph @xmath1 is closed if and only if for all vertices @xmath46 $ ] , all shortest paths from @xmath11 to @xmath12 are directed .      given a vertex @xmath29 , the _ neighborhood _ of @xmath27 in @xmath1 is @xmath47 when @xmath1 is labeled and @xmath48 $ ] , we have a disjoint union @xmath49 where @xmath50 this is the notation used in @xcite , where it is shown that a labeling is closed if and only if @xmath51 and @xmath52 are complete for all @xmath48 $ ] . 
   vertices @xmath53 $ ] with @xmath54 give the _ interval _ 
   @xmath55 = \{k \in [ n ] 
   \mid i \le k \le j\}$ ] . here is a characterization of when a labeling of a connected graph is closed . 
   [ nbdinterval ] a labeling on a connected graph @xmath1 is closed if and only if for all @xmath48 $ ] , @xmath51 is complete and equal to @xmath56 $ ] , @xmath57 . 
   assume that the labeling is closed . 
   then definition  [ closeddef ] easily implies that @xmath51 is complete . 
   it remains to show that @xmath51 is an interval of the desired form . 
   pick @xmath58 and @xmath59 $ ] with @xmath60 . 
   a shortest path @xmath61 from @xmath62 to @xmath63 is directed by proposition  [ directed ] . since @xmath64 
   , we have @xmath65 . 
   thus @xmath66 and hence @xmath67 since @xmath68 is complete . since @xmath69 , we have @xmath70 . 
   we now prove by induction that @xmath71 for all @xmath72 . 
   the base case is proved in the previous paragraph . 
   now assume @xmath73 . 
   then @xmath74 since @xmath75 and the labeling is closed . 
   this completes the induction . 
   since @xmath63 , it follows that @xmath76 . 
   then we have @xmath77 with @xmath78 . 
   thus @xmath79 since the labeling is closed , so @xmath80 since @xmath64 . 
   hence @xmath51 is an interval of the desired form . 
   conversely , suppose that @xmath51 is complete and @xmath81 $ ] , @xmath57 , for all @xmath82 . 
   take @xmath6 with @xmath7 or @xmath8 . 
   the former implies @xmath9 since @xmath68 is complete . 
   for the latter , assume @xmath83 . 
   then @xmath84 with @xmath85 . 
   since @xmath86 is an interval containing @xmath87 and @xmath11 , @xmath86 also contains @xmath15 . 
   hence @xmath9 . 
   the following subsets of @xmath2 will play a key role in what follows . 
   [ layerdef ] let @xmath1 be a connected graph labeled so that @xmath88 $ ] . 
   then the _ @xmath89 layer of @xmath1 _ is the set @xmath90 \mid d(i,1 ) = n\}.\ ] ]    thus @xmath91 consists of all vertices that are distance @xmath92 from the vertex @xmath93 . 
   note that @xmath94 and @xmath95 . 
   furthermore , since @xmath1 is connected , we have a disjoint union @xmath96 where @xmath97\}$ ] . 
   we omit the easy proof of the following lemma . 
   [ layerlem ] let @xmath1 be a connected graph labeled so that @xmath98 $ ] . 
   then :    1 .   if @xmath99 and @xmath10 , then @xmath100 , @xmath91 , or @xmath101 . 
   if @xmath30 is a path in @xmath1 connecting @xmath99 to @xmath102 with @xmath103 , then for every integer @xmath104 , there exists @xmath105 with @xmath106 . 
   [ layerprop ] let @xmath1 be a connected graph with a closed labeling satisfying @xmath42 $ ] . 
   then :    1 . 
   each layer @xmath91 is complete . 
   2 .   if @xmath107 , then @xmath108 . 
   we first show that @xmath109 to see why , take a shortest path from 1 to @xmath110 . 
   this path has length @xmath111 , so appending the edge @xmath112 gives a path of length @xmath113 to @xmath114 . 
   since @xmath115 , this is a shortest path and hence is directed by proposition  [ directed ] . 
   thus @xmath116 .    for ( 1 ) , we use induction on @xmath117 . 
   the base case is trivial since @xmath118 . 
   now assume @xmath91 is complete and take @xmath119 with @xmath120 . 
   a shortest path @xmath121 from @xmath93 to @xmath122 has a vertex @xmath123 adjacent to @xmath11 , and a shortest path @xmath124 from @xmath93 to @xmath125 has a vertex @xmath126 adjacent to @xmath12 
   . then @xmath127 and @xmath128 by .    if @xmath129 , then @xmath130 , which implies @xmath131 since the labeling is closed . 
   if @xmath132 , then @xmath133 since @xmath91 is complete . 
   assume @xmath134 . then @xmath135 and closed imply @xmath136 . 
   since @xmath137 and @xmath138 , we have @xmath139 by . 
   then @xmath140 and closed imply @xmath131 . 
   hence @xmath101 is complete . 
   we now turn to ( 2 ) . to prove @xmath141 , @xmath142 , take @xmath138 . 
   a shortest path from @xmath93 to @xmath11 will have a vertex @xmath143 such that @xmath144 
   . then @xmath127 by , hence @xmath145 . 
   also , @xmath146 since @xmath147 . if @xmath148 , then @xmath149 . if @xmath150 , then @xmath151 since @xmath91 is complete . 
   then @xmath152 and closed imply @xmath153 , and then @xmath154 by . 
   thus @xmath149 .    to prove the opposite inclusion , 
   take @xmath149 . 
   since @xmath153 and @xmath155 , we have @xmath156 for @xmath157 by lemma  [ layerlem ] . 
   if @xmath158 , then would imply @xmath159 , contradicting @xmath160 . if @xmath161 , then @xmath162 , again contradicting @xmath163 . 
   hence @xmath122 . 
   when the labeling of a connected graph is closed , the diameter of the graph determines the number of layers as follows . 
   [ diameters ] let @xmath1 be a connected graph with a closed labeling . 
   then :    1 . 
   @xmath164 is the largest integer @xmath165 such that @xmath166 . 
   if @xmath30 is a longest shortest path of @xmath1 , then one endpoint of @xmath30 is in @xmath167 or @xmath168 and the other is in @xmath169 , where @xmath170 .    for ( 1 ) 
   , let @xmath165 be the largest integer with @xmath171 . 
   since points in @xmath169 have distance @xmath165 from @xmath93 , we have @xmath172 .    for the opposite inequality 
   , it suffices to show that @xmath173 for all @xmath174 with @xmath175 . 
   we can assume @xmath1 has more than one vertex , so that @xmath176 . 
   suppose @xmath161 and @xmath177 with @xmath178 . 
   if @xmath179 , then @xmath180 and @xmath181 since @xmath102 . also , 
   if @xmath182 , then @xmath183 , so that @xmath184 since @xmath91 is complete by proposition  [ layerprop ] . 
   finally , if @xmath185 , let @xmath186 for each integer @xmath187 . by proposition  [ layerprop ] , we know that @xmath188 . hence , if @xmath189 
   , then @xmath190 is a path of length @xmath191 . 
   if @xmath192 , then @xmath193 is a path of length @xmath194 . 
   thus we have a path from @xmath11 to @xmath12 of length at most @xmath191 , so that @xmath195 .    for ( 2 ) , let @xmath11 and @xmath12 be the endpoints of the longest shortest path @xmath30 with @xmath161 , @xmath177 and @xmath178 . if @xmath196 , then the previous paragraph implies @xmath197 which forces @xmath198 ( so @xmath199 ) and @xmath200 ( so @xmath201 ) . 
   the remaining cases @xmath202 and @xmath203 are straightforward and are left to the reader . 
   recall from definition  [ narrowdef ] that a connected graph @xmath1 is narrow when every vertex is distance at most one from every longest shortest path . 
   narrowness is a key property of connected closed graphs . 
   [ narrowthm ] every connected closed graph is narrow . 
   let @xmath1 be a connected graph with a closed labeling . pick a vertex @xmath204 and a longest shortest path @xmath30 . since @xmath1 is connected , @xmath161 for some integer @xmath92 . by proposition  [ diameters ] , 
   the endpoints of @xmath30 lie in @xmath167 or @xmath168 and @xmath169 , @xmath205 . 
   then lemma  [ layerlem ] implies that @xmath30 has a vertex @xmath206 in @xmath207 for every @xmath208 .    if @xmath209 , then either @xmath210 or @xmath211 , in which case @xmath212 since @xmath91 is complete by proposition  [ layerprop ] . on the other hand , if @xmath202 , then @xmath213 , hence @xmath180 . 
   then @xmath214 since @xmath215 . in either case 
   , @xmath11 is distance at most one from @xmath30 . 
   we introduce algorithm  [ alg : labeling ] , which labels the vertices of a connected graph . 
   this algorithm will play a key role in the proof of theorem  [ mainthm ] . 
   [ alg : input ] [ alg : output ] @xmath216 @xmath217 @xmath218 endpoint of a longest shortest path with minimal degree[alg : possible1 ] label @xmath219 as @xmath11 [ alg : label1 ] 
   @xmath220[alg : function1 ] @xmath221 @xmath222 @xmath223[alg : labelj1 ]    the algorithm works as follows . among the endpoints of all longest shortest paths , we select one of minimal degree and 
   label it as @xmath93 . 
   we then go through the vertices in @xmath224 and label them @xmath225 , first labeling vertices with the fewest number of edges connected to unlabeled vertices . 
   this process is repeated for the unlabeled vertices connected to vertex  @xmath226 , and vertex @xmath227 , and so on until every vertex is labeled . 
   furthermore , every vertex will be labeled because we first label everything in @xmath228 , then label everything in @xmath229 not already labeled , and so on . since the input graph is connected , this process must eventually reach all of the vertices . 
   hence we get a labeling of @xmath1 . 
   the following lemma explains the function @xmath230 that appears in algorithm  [ alg : labeling ] . 
   [ claim : meaningoffunction ] let @xmath1 be a connected graph with the labeling from algorithm  [ alg : labeling ] . then :    1 . 
   @xmath231 , and for every @xmath232 $ ] with @xmath233 , @xmath234 . 
   2 .   if @xmath235 , then @xmath236 .    algorithm  [ alg : labeling ] defines @xmath231 . 
   now assume @xmath233 and let @xmath27 be the vertex assigned the label @xmath11 . by lines  [ alg : label2 ] and [ alg : function2 ] of the algorithm , we need to show that when the label @xmath11 is assigned to @xmath27 , the variable @xmath12 equals @xmath237 . 
   this follows because for any smaller value @xmath238 , line  [ alg : secondloop ] implies that everything in the neighborhood of @xmath239 is labeled before @xmath239 is incremented . 
   however , lines  [ alg : sset][alg : beginsecondloop ] show that @xmath27 is adjacent to @xmath12 and unlabeled at the start of the loop on line  [ alg : secondloop ] 
   . hence @xmath27 can not link to any smaller value of @xmath12 , and since @xmath27 has label @xmath11 , @xmath240 follows . 
   \(2 ) suppose that @xmath241 $ ] satisfy @xmath235 . since @xmath242 ( resp . 
   @xmath243 ) is the value of @xmath12 when the label @xmath244 ( resp . 
   @xmath114 ) was assigned in algorithm  [ alg : labeling ] , @xmath235 implies that the label @xmath114 was assigned later than @xmath244 in the algorithm . 
   since the labels are assigned in numerical order , we must have @xmath245 . 
   the labeling produced by algorithm  [ alg : labeling ] allows us to define the layers @xmath91 . 
   these interact with the function @xmath230 as follows :    [ claim : orderingclaim ] let @xmath1 be a connected graph with the labeling from algorithm  [ alg : labeling ] . 
   then :    1 .   if @xmath246 , then @xmath247 if @xmath248 . 
   2 .   if @xmath246 and @xmath249 with @xmath250 , then @xmath236 . 
   we prove ( 1 ) and ( 2 ) simultaneously by induction on @xmath209 ( the case @xmath202 of ( 2 ) is trivially true ) . 
   the first time algorithm  [ alg : labeling ] gets to line  [ alg : sset ] , we have @xmath251 . 
   every vertex in @xmath252 , is labeled during the loop starting on line  [ alg : firstloop ] , so @xmath253 for all @xmath254 . 
   hence ( 1 ) holds when @xmath255 . 
   also , if @xmath249 with @xmath256 , then the vertex @xmath114 is not labeled at this stage . since labels are assigned in numerical order , we must have @xmath236 for all @xmath254 . 
   hence ( 2 ) holds when @xmath198 . 
   now assume that ( 1 ) and ( 2 ) hold for @xmath111 and every @xmath257 . 
   given @xmath258 , a shortest path from 1 to @xmath244 gives @xmath259 with @xmath260 . 
   since @xmath261 by lemma  [ claim : meaningoffunction](1 ) , we have @xmath262 . 
   we have @xmath263 for some @xmath187 . 
   if @xmath264 , then the inductive hypothesis for ( 2 ) would imply @xmath265 , which contradicts @xmath262 . 
   hence @xmath263 for some @xmath266 . but @xmath267 and @xmath268 imply @xmath269 for @xmath270 by lemma  [ layerlem](1 ) . 
   hence @xmath271 , proving ( 1 ) for @xmath272 . 
   turning to ( 2 ) , pick @xmath258 and @xmath249 with @xmath273 . 
   we just showed that @xmath274 , and lemma  [ layerlem](1 ) implies that @xmath275 , @xmath276 , since @xmath277 . 
   then @xmath278 , so our inductive hypothesis , applied to @xmath279 and @xmath280 , implies @xmath235 
   . then @xmath236 by lemma  [ claim : meaningoffunction](2 ) , proving ( 2 ) for @xmath272 . 
   we now turn to the main result of the paper . 
   theorem  [ mainthm ] from the introduction states that a connected graph is closed if and only if it is chordal , claw - free and narrow . 
   one direction is now proved , since closed graphs are chordal and claw - free by proposition  [ hprop ] , and connected closed graphs are narrow by theorem  [ narrowthm ] . 
   the proof of converse is harder . 
   the key idea that the labeling constructed by algorithm  [ alg : labeling ] is closed when the input graph is chordal , claw - free and narrow . 
   thus the proof of theorem  [ mainthm ] will be complete once we prove the following result . 
   [ converse ] let @xmath1 be a connected , chordal , claw - free , narrow graph 
   . then the labeling produced by algorithm  [ alg : labeling ] is closed .    by proposition  [ nbdinterval ] , it suffices to show that the labeling produced by algorithm  [ alg : labeling ] has the property that for all @xmath281 $ ] , @xmath282 \text { for } r_m = |{n_g^>}(m)|.\ ] ] we will prove this by induction on @xmath283 . in below , we show that holds for @xmath284 , and in below , we show that if holds for all @xmath285 , then it also holds for @xmath283 . 
   thus , we will be done after proving and .      after algorithm [ alg : labeling ] runs on a chordal 
   , claw - free and narrow graph @xmath1 , the base case of the induction in the proof of theorem  [ converse ] is the following assertion : @xmath286,\ r = |{n_g^>}(1)|,\ \text{and } { n_g^>}(1 ) \text { is    complete } .\ ] ] we will first show that @xmath287 $ ] , @xmath288 . 
   the first time through the the loop beginning on line  [ alg : firstloop ] in algorithm  [ alg : labeling ] , @xmath289 and @xmath290 and @xmath291 . for each vertex in @xmath292 , the loop beginning on line  [ alg : secondloop ] 
   labels that vertex @xmath11 , removes it from @xmath292 , and increments @xmath11 . 
   this continues until @xmath293 , at which point every vertex in @xmath292 has been labeled @xmath294 , where @xmath295 is the initial size of @xmath292 . hence @xmath296 $ ] .    to prove that @xmath228 is complete , there are several cases to consider . 
   pick distinct vertices @xmath297 and assume that @xmath298 . 
   note that @xmath299 are distance @xmath226 apart and therefore @xmath300 . 
   our choice of vertex @xmath93 guarantees that there is a longest shortest path @xmath30 with 1 as an endpoint . 
   let @xmath301 be the other , so that @xmath302 , @xmath303 and @xmath304 . 
   since @xmath305 is the only vertex of @xmath30 in @xmath168 , @xmath114 and @xmath244 can not both lie on @xmath30 .    therefore , either @xmath306 , @xmath307 , or @xmath308 . 
   we will show that each possibility leads to a contradiction , proving that @xmath309 .    plus 1 pt minus 1 pt    * case 1 . * both @xmath308 . 
   if @xmath114 has distance @xmath310 from @xmath311 , then appending the edge @xmath312 to a shortest path from @xmath114 to @xmath311 gives a longest shortest path @xmath313 from @xmath93 to @xmath311 that contains @xmath114 . 
   replacing @xmath30 with @xmath313 , we get @xmath314 , which is case 2 to be considered below . similarly , 
   if @xmath244 has distance @xmath310 from @xmath311 , then replacing @xmath30 allows us to assume @xmath315 , which is also covered by case 2 below . 
   thus we may assume that neither @xmath114 nor @xmath244 has distance @xmath310 from @xmath311 . 
   since @xmath316 would imply @xmath317 , we conclude that @xmath114 has distance @xmath165 from @xmath311 , and the same holds for @xmath244 . 
   it follows that @xmath318 , since otherwise there is a path shorter than length @xmath165 from @xmath114 or @xmath244 to @xmath311 . 
   since the subgraph induced on vertices @xmath319 can not be a claw , either @xmath320 or @xmath321 or both . 
   we consider each possibility separately .    plus 
   1 pt minus 1 pt    * case 1a . 
   * both @xmath322 , @xmath321 , as shown in figure  1(a ) on the next page . 
   then the subgraph induced on @xmath323 is a claw , contradicting our assumption of claw - free . 
   -10pt @xmath324 ( n1 )   at ( 2,1 ) { $ 1\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( s )   at ( 3.5,3 )   { $ s\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( t ) at ( .5,3 ) { $ t\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( v1 ) at ( 2,3 ) { $ v_1\rule[-2.5pt]{0pt}{10pt}$ } ;     \node[vertex ] ( v2 ) at ( 2,5 ) { $ v_2\rule[-2.5pt]{0pt}{10pt}$ } ;      \foreach \from/\to in { n1/v1,n1/t , n1/s , v1/v2,s / v1,t / v1 }   \draw ( \from)--(\to ) ;      \node [ right , font = \large ] at ( 4.2,3 ) { $ l_1 $ } ;    \node [ right , font=\large ] at ( 4.2,5 ) { $ l_2 $ } ;    \node [ right , 
   font = \large ] at ( 4.2,1 ) { $ l_0 $ } ;    \node [ right ] at ( 2.5,.3 ) { ( a ) } ;    \end{tikzpicture } & \hspace{25pt}\begin{tikzpicture }    \node[vertex ] ( n1 )   at ( 2,1 ) { $ 1\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( s )   at ( 3.5,3.2 )   { $ s\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( t ) at ( .5,3.2 ) { $ t\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( v1 ) at ( 2,3.2 ) { $ v_1\rule[-2.5pt]{0pt}{10pt}$ } ;     \node[vertex ] ( v2 ) at ( 2,5.4 ) { $ v_2\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( t2 ) at ( .5,5.4 ) { $ t_2\rule[-2.5pt]{0pt}{10pt}$ } ;      \foreach \from/\to in { n1/s , n1/t , n1/v1 , v1/v2 , s / v1,t / t2 }   \draw ( \from)--(\to ) ;      \node [ right , font = \large ] at ( 4.3,3.2 ) { $ l_1 $ } ;    \node [ right , font=\large ] at ( 4.3,5.4 ) { $ l_2 $ } ;    \node [ right , font = \large ] at ( 4.3,1 ) { $ l_0 $ } ;    \node [ right ] at ( 2.5,.3 ) { ( b ) } ;    \end{tikzpicture }   \end{array}\ ] ] -8pt    plus 1 pt minus 1 pt    * case 1b . * exactly one of @xmath325 is in @xmath3 . without loss of generality , we may assume @xmath326 and @xmath327 , as shown in figure  1(b ) . 
   recall that @xmath328 and @xmath244 is distance @xmath165 to @xmath311 . 
   since @xmath244 and @xmath93 are both endpoints of longest shortest paths , line  [ alg : possible1 ] of algorithm  [ alg : labeling ] implies that @xmath329 . since @xmath330 is adjacent to @xmath93 but not 
   @xmath244 , there must be at least one @xmath331 adjacent to @xmath244 but not @xmath93 , i.e. , @xmath332 with @xmath333 .    for this @xmath331 
   , it follows that @xmath334 . 
   we also have @xmath335 since @xmath328 . furthermore , 
   @xmath336 , since otherwise we would have the @xmath37-cycle @xmath337 with no chords as @xmath338 , @xmath339 . 
   similarly , @xmath340 or else we would have the @xmath37-cycle @xmath341 with no chords since @xmath338 , @xmath327 . 
   note also that @xmath342 , since otherwise we would have the @xmath343-cycle @xmath344 with no chords as @xmath345 , @xmath346 , @xmath347 , @xmath348 , @xmath340 , contradicting chordal . 
   hence @xmath331 gives figure  1(b ) as an induced subgraph . 
   since @xmath1 is narrow , either @xmath349 or @xmath331 is adjacent to a vertex of @xmath30 . 
   however , @xmath349 would imply @xmath350 since both lie in @xmath351 , contradicting @xmath352 . 
   thus @xmath353 for some @xmath354 . 
   since @xmath355 and @xmath356 , we have @xmath357 by lemma  [ layerlem](1 ) . 
   we just proved @xmath342 , so we must have @xmath358 . 
   this gives the @xmath359-cycle @xmath360 . 
   since figure  1(b ) is an induced subgraph , the only possible chords are @xmath361 , @xmath362 , @xmath363 , but by lemma  [ layerlem](1 ) none of these are in @xmath3 since @xmath364 and @xmath365 . 
   hence the @xmath359-cycle has no chords , contradicting chordal .    * case 2 . 
   * @xmath314 or @xmath366 . 
   we may assume @xmath367 . 
   arguing as in case 1b , there is @xmath332 with @xmath333 and @xmath334 . 
   we also have @xmath368 , since otherwise the @xmath37-cycle @xmath369 has no chords as @xmath370 , @xmath371 . 
   since @xmath1 is narrow , @xmath331 must either be in @xmath30 or be adjacent to a vertex in @xmath30 . 
   however , @xmath372 would imply @xmath373 since @xmath374 , and the latter would give @xmath375 , which we just showed to be impossible . 
   hence @xmath376 , so that @xmath377 for some @xmath187 . 
   note that @xmath378 by lemma  [ layerlem](1 ) . 
   we claim that @xmath379 .    to see why , first note that @xmath380 , since otherwise we would have the @xmath37-cycle @xmath381 with no chords as @xmath370 , @xmath382 . 
   we also know that @xmath342 , as otherwise we would have the @xmath343-cycle @xmath383 with no chords since @xmath384 , @xmath338 , @xmath385 , @xmath347 , @xmath386 . 
   see figure  2(a ) . 
   thus we must have @xmath387 . 
   however , this gives a @xmath359-cycle @xmath388 with the same impossible chords as before along with @xmath362 , @xmath361 , @xmath389 , @xmath390 , as in figure  2(b ) . 
   this contradicts chordal , and follows . 
   @xmath391 ( n1 )   at ( 2,1 ) { $ 1\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n2 )   at ( 1,3 )   { $ t\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n3 ) at ( 3,3 ) { $ s\rule[-2.5pt]{0pt}{10pt}$ } ;      \node[vertex ] ( n4 ) at ( 1,4.5){$t_2\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n5 ) at ( 3,4.5){$v_2\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n6 ) at ( 3,6){$v_3\rule[-2.5pt]{0pt}{10pt}$ } ;      \foreach \from/\to in { n1/n2,n1/n3,n2/n4 , n3/n5 , n6/n5 } \draw ( \from)--(\to ) ; ;   \foreach \from/\to in { n4/n5 } \draw[dotted ] ( \from)--(\to ) ;      \node [ right , font = \large ] at ( 3.7,3 ) { $ l_1 $ } ;    \node [ right , font=\large ] at ( 3.7,4.5 ) { $ l_2 $ } ;    \node [ right , font = \large ] at ( 3.7,1 ) { $ l_0 $ } ;    \node [ right , font = \large ] at ( 3.7,6 ) { $ l_3 $ } ;      \node [ right ] at ( 2.5,.3 ) { ( a ) } ;    \end{tikzpicture}&\hspace{25pt } & \begin{tikzpicture }    \node[vertex ] ( n1 )   at ( 2,1 ) { $ 1\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n2 )   at ( 1,3 )   { $ t\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n3 ) at ( 3,3 ) { $ s\rule[-2.5pt]{0pt}{10pt}$ } ;      \node[vertex ] ( n4 ) at ( 1,4.5){$t_2\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n5 ) at ( 3,4.5){$v_2\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n6 ) at ( 3,6){$v_3\rule[-2.5pt]{0pt}{10pt}$ } ;      \foreach \from/\to in { n1/n2,n1/n3,n2/n4 , n3/n5 , n6/n5 } \draw ( \from)--(\to ) ; ;   \foreach \from/\to in { n4/n6 } \draw[dotted ] ( \from)--(\to ) ;      \node [ right , font = \large ] at ( 3.7,3 ) { $ l_1 $ } ;    \node [ right , font=\large ] at ( 3.7,4.5 ) { $ l_2 $ } ;    \node [ right , font = \large ] at ( 3.7,1 ) { $ l_0 $ } ;    \node [ right , font = \large ] at ( 3.7,6 ) { $ l_3 $ } ;      \node [ right ] at ( 2.5,.3 ) { ( b ) } ;    \end{tikzpicture } \end{array}\ ] ] -8pt      after algorithm [ alg : labeling ] runs on a chordal , claw - free and narrow graph @xmath1 , we now prove that the resulting labeling satsifies the inductive step in the proof of theorem  [ converse ] : @xmath392 $ , $ r_u = |{n_g^>}(u)|$ , $ { n_g^>}(u)$ is      complete , $ 1\leq u < m$ , } \\ & \text{then $ { n_g^>}(m ) = [ m+1,m+r_m]$ ,      $ r_m = |{n_g^>}(m)|$ , and $ { n_g^>}(m)$ is complete . } \end{aligned}\ ] ]    for the first assertion of , we know that @xmath393 $ ] is complete , which implies that @xmath394 . by analyzing the loop beginning on line  [ alg : secondloop ] at this stage of algorithm  [ alg : labeling ] 
   , one finds that every vertex in @xmath292 will be labeled with consecutive integers , starting at @xmath395 and continuing until the final vertex in @xmath396 is labeled @xmath397 , where @xmath295 is the original size of @xmath292 . 
   it follows that @xmath396 is an interval of the desired form .    to show that @xmath398 is complete , pick @xmath399 in @xmath398 . 
   let @xmath400 be a shortest path from @xmath303 to @xmath401 , with @xmath356 for all @xmath187 . 
   lemmas  [ layerlem](1 ) and  [ claim : orderingclaim](2 ) imply that @xmath402 . 
   hence , @xmath114 and @xmath244 are either both distance @xmath403 from 1 , both distance @xmath404 from 1 , or one of @xmath114 and @xmath244 is distance @xmath404 from 1 and the other is distance @xmath403 from 1 . 
   we consider each case separately . 
   plus3pt minus2pt    * case 1 . * @xmath405 
   . then @xmath406 , @xmath407 by lemma  [ layerlem](1 ) . 
   since the subgraph induced on @xmath408 can not be a claw , we must have @xmath409 .    plus3pt minus2pt    * case 2 . 
   * @xmath410 . 
   we can assume @xmath411 and choose a shortest path @xmath412 from @xmath413 to @xmath414 with @xmath415 . 
   then @xmath416 by lemma  [ claim : orderingclaim](2 ) , giving @xmath417 . since @xmath418 and @xmath419 is an interval by hypothesis , we have @xmath420 . 
   but then @xmath309 since we are also assuming that @xmath419 is complete .    plus3pt minus2pt    * case 3 . 
   *    we can assume @xmath421 and @xmath422 , so @xmath411 by lemma  [ claim : orderingclaim](2 ) . 
   we also have @xmath423 by lemma  [ claim : meaningoffunction](2 ) since @xmath424 . 
   we will consider separately the two possibilities that @xmath425 and @xmath426 . 
   plus3pt minus2pt    * case 3a . 
   * suppose that @xmath427 . 
   then @xmath428 since @xmath429 by lemma  [ claim : meaningoffunction](1 ) . 
   we also have @xmath430 , for otherwise we would have @xmath431 since @xmath261 
   . then @xmath432 , which implies @xmath236 by lemma  [ claim : meaningoffunction](2 ) , contradicting @xmath411 . 
   since the subgraph induced on @xmath433 can not be a claw , we must have @xmath409 . 
   plus3pt minus2pt    * case 3b . 
   * suppose that @xmath426 . 
   we will assume @xmath434 and derive a contradiction . 
   the equality @xmath426 means that @xmath283 and @xmath114 were both labeled when @xmath435 in the loop starting on line  [ alg : firstloop ] of algorithm  [ alg : labeling ] . 
   consider the moment in the algorithm when the label @xmath283 is assigned . since @xmath436 and @xmath435 , this happens during an iteration of the loop on line  [ alg : secondloop ] for which @xmath437 . 
   line  [ alg : beginsecondloop ] guarantees that the vertices assigned the labels @xmath283 and @xmath114 satisfy @xmath438 . 
   since @xmath114 is not yet labeled at this point and @xmath411 , @xmath244 is also not yet labeled and therefore @xmath439 . 
   it follows that @xmath440 and @xmath441 . 
   but , in order for @xmath442 to hold , there must be @xmath443 with @xmath444 and @xmath445 and @xmath446 . 
   let us study @xmath447 . if @xmath448 , then @xmath449 . 
   but we also have @xmath450 . 
   since @xmath451 , @xmath452 is complete by the hypothesis of , so we would have @xmath453 . 
   this contradicts our choice of @xmath447 . 
   hence @xmath454 . 
   we also have @xmath455 , since otherwise the @xmath37-cycle @xmath456 would have no chords as @xmath457 . 
   also , since @xmath458 , lemma  [ claim : orderingclaim](1 ) implies that @xmath459 . 
   we claim that @xmath460 . 
   lemma  [ layerlem](1 ) , @xmath461 , and @xmath462 imply that @xmath463 or @xmath464 . 
   if @xmath463 , then @xmath465 by lemma  [ claim : orderingclaim](2 ) . from here 
   , @xmath466 implies @xmath467 by lemma  [ claim : orderingclaim](2 ) . 
   hence we have @xmath468 . 
   the hypothesis of implies that @xmath469 is complete and is an interval . since @xmath470 
   , it follows that @xmath471 , which contradicts our choice of @xmath447 . 
   hence @xmath460 and we have figure  3(a ) . 
   @xmath391 ( n1 )   at ( 2,1 ) { $ j\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n2 )   at ( 1,3 )   { $ m\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n3 ) at ( 3,3 ) { $ s\rule[-2.5pt]{0pt}{10pt}$ } ;      \node[vertex ] ( n4 ) at ( 1,4.5){$t\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n5 ) at ( 3,4.5){$s_2\rule[-2.5pt]{0pt}{10pt}$ } ;      \foreach \from/\to in { n1/n2,n1/n3,n2/n3,n2/n4 , n3/n5 } \draw ( \from)--(\to ) ; ;      \node [ vertex , font = \large ] at ( 4,3 ) { $ l_q$ } ;    \node [ vertex , font=\large ] at ( 4,4.5 ) { $ l_{q+1}$ } ;    \node [ vertex , font = \large ] at ( 4,1 ) { $ l_{q-1}$ } ;      \node [ right ] at ( 2.5,.3 ) { ( a ) } ;    \end{tikzpicture}&\hspace{25pt } & \begin{tikzpicture }    \node[vertex ] ( n1 )   at ( 2,1 ) { $ j\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n2 )   at ( 1,3 )   { $ m\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n3 ) at ( 3,3 ) { $ s\rule[-2.5pt]{0pt}{10pt}$ } ;      \node[vertex ] ( n4 ) at ( 1,4.5){$t\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n5 ) at ( 3,4.5){$s_2\rule[-2.5pt]{0pt}{10pt}$ } ;    \node[vertex ] ( n6 ) at ( 1,6){$w_{q+2}$ } ;      \foreach \from/\to in { n1/n2,n1/n3,n2/n3,n2/n4 , n3/n5 , n4/n6 , 
   n6/n5 } \draw ( \from)--(\to ) ; ;      \node [ right , font = \large ] at ( 4,3 ) { $ l_q$ } ;    \node [ right , font=\large ] at ( 4,4.5 ) { $ l_{q+1}$ } ;    \node [ right , font = \large ] at ( 4,1 ) { $ l_{q-1}$ } ;    \node [ right , font = \large ] at ( 4,6 ) { $ l_{q+2}$ } ;      \node [ right ] at ( 2.5,.3 ) { ( b ) } ;    \end{tikzpicture } \end{array}\ ] ] -10pt    let @xmath311 be a vertex of distance @xmath170 from @xmath93 and pick a longest shortest path @xmath472 from @xmath413 to @xmath473 , so @xmath415 . 
   since @xmath1 is narrow , @xmath244 and @xmath447 must each either be in @xmath124 or be adjacent to a vertex in @xmath124 . 
   we will consider each of these cases . 
   _ first _ , suppose that @xmath474 . 
   then @xmath422 implies that @xmath475 . since @xmath476 
   , there is a path of length @xmath477 connecting @xmath93 to @xmath478 . using @xmath479 , it follows that @xmath480 is a path of length @xmath170 . 
   since @xmath1 is narrow , @xmath447 must be adjacent to some vertex @xmath481 . 
   then @xmath482 , @xmath483 and lemma  [ layerlem](1 ) imply that @xmath484 . 
   this gives the @xmath343-cycle @xmath485 with no chords since @xmath482 , @xmath486 , @xmath298 and @xmath487 , @xmath488 since @xmath489 but @xmath490 . 
   see figure  3(b ) . 
   hence we have a contradiction since @xmath1 is chordal . 
   _ second _ , suppose that @xmath491 
   . then @xmath492 . 
   arguing as in the _ first _ , we arrive at figure  3(b ) with the same @xmath343-cycle with no chords , again a contradiction . 
   _ third _ , suppose that @xmath493 . 
   first note that @xmath124 was an arbitrary longest shortest path starting at @xmath93 . 
   thus the above _ first _ and _ second _ give a contradiction whenever @xmath447 or @xmath244 are on _ any _ longest shortest path starting at @xmath93 . 
   hence we may assume that @xmath447 and @xmath244 are not on any shortest path of length @xmath165 starting at @xmath93 . 
   since @xmath1 is narrow , @xmath460 is adjacent to a vertex of @xmath124 , which must be @xmath494 , @xmath495 , or @xmath496 by lemma  [ layerlem](1 ) . 
   however , if @xmath484 , then we would get a path of length @xmath165 from @xmath93 to @xmath311 by taking any shortest path from 1 to @xmath447 , followed by @xmath497 , and then continuing along @xmath124 from @xmath496 to @xmath311 . 
   this longest shortest path starts at @xmath93 and contains @xmath447 , contradicting the previous paragraph . 
   hence @xmath498 and @xmath447 must be adjacent to @xmath494 or @xmath495 , and the same is true for @xmath244 by a similar argument . 
   in fact , we must have @xmath499 , since otherwise @xmath500 and the subgraph induced on @xmath501 would be a claw . 
   a similar argument shows that @xmath502 . since @xmath503 and @xmath504 
   , this implies that the subgraph induced on @xmath505 is a claw , again contradicting claw - free . 
   this final contradiction completes the proof of , and theorem  [ converse ] is proved .    [ 
   remark : ching ] in and , the chordal hypothesis is applied only to cycles of length @xmath37 , @xmath343 , or @xmath359 . 
   hence , in theorem  [ mainthm ] and corollary  [ cormainthm ] , we can replace chordal with the weaker hypothesis that all cycles of length @xmath37 , @xmath343 , or @xmath359 have a chord . 
   theorem  [ mainthm ] is based on the senior honors thesis of the second author , written under the direction of the first author . 
   we are grateful to amherst college for the post - baccalaureate summer research fellowship that supported the writing of this paper . 
   thanks also to michael ching for remark  [ remark : ching ] . 
   m.  crupi and g.  rinaldo , _ binomial edge ideals with quadratic grbner bases _ , electron . 
   j.  combin . 
   * 18 * ( 2011 ) , paper 211 , 13pp . 
   v.  ene , j.  herzog and t.  hibi , _ cohen - macaulay binomial edge ideals _ , nagoya math .  j.  * 204 * ( 2011 ) , 5768 . 
   v.   ene , j ,  herzog and t.  hibi , _ koszul binomial edge ideals _ , 
   arxiv:1310.6426 [ math.ac ] . v.  ene , j.  herzog and t.  hibi , _ linear flags and koszul filtrations _ , arxiv:1312.2190 [ math.ac ] . v.  ene and a.  zarojanu , _ on the regularity of binomial edge ideals _ , arxiv:1307.2141 [ math.ac ] . j.  herzog , t.  hibi , f.  hreinsdttir , t.  kahle and j.  rauh , _ binomial edge ideals and conditional independence statements _ , adv .  in appl . 
   * 45 * ( 2010 ) , 317333 . 
   m.  ohtani , _ graphs and ideals generated by some 2-minors _ , commun . 
   algebra * 39 * ( 2011 ) , 905917 . 
   j.  rauh , _ 
   generalized binomial edge ideals _ , adv .  in appl . 
   * 50 * ( 2013 ) , 409414 . 
   s.  saeedi madani and d. kiani , _ binomial edge ideals of graphs _ , electron . 
   j.  combin . 
   * 19 * ( 2012 ) , paper 44 , 6pp .
summary: a graph is closed when its vertices have a labeling by @xmath0 $ ] with a certain property first discovered in the study of binomial edge ideals . in this article 
   , we prove that a connected graph has a closed labeling if and only if it is chordal , claw - free , and has a property we call _ narrow _ , which holds when every vertex is distance at most one from all longest shortest paths of the graph .