El tamaño de un grafo con cintura inferiormente acotada

El tama ñ o de un grafo con cintura interiormente acotada © E . Abajo , A . Di á nez Departamento de Matemdttea Aplicada I , Universidad de Semita . E - mail : eabajoQus . es , anadianezQus . es Resumen . Por ex ( ^ ًا { C 3٠ , . . . , ى grafo simple de orden V y libre de ciclos de longitud menor o igual que n , con n > 4 . Obtenemos , para V < L ( 16 ft - 15 ) / 5 لا su valor exacto y todas las posibles cinturas de los grafos extremales . Adem á s , demostramos que para cada n > 21 og 2 ( todo grafo extremal G con e { G ) - i / ( G ) = k se obtiene a ñ adiendo v é rtices de valencia 1 y / o subdividiendo aristas de un grafo 0 multigrafo H con ó ( H ) 3 y e ( H ) - v ( H ) = k . Por otra parte , se aportan valores exactos de la funci ó n extremal para 71 = 5 , 6 , 7 . Palabras clare . Funci ó n extremal , grajos extr é males , cintura , ciclos prohibidos . entendemos el m á ximo n ú mero de aristas de un 2 k + 2 ) con k > 0 3 INTRODUCCI ó N I Para notaci ó n y terminolog í a no definida en este trabajo se puede consultar [ 1 ] . Este articulo se enmarca dentro de la Teor í a Extremal de Grafos . Denotamos por V ( G ) y E ( G ) al conjunto de los v é rtices y las aristas de G ) respectivamente . Al orden y al tama ñ o de G por | ^ ( G ) | = i / ( G ) y | E ( G ) | = e ( G ) . Si G contiene ciclos , entonces la cintura de G , g { G ) ) es la longitud del menor ciclo contenido en G . Por Gn denotamos al ciclo de longitud 71 , 71 > 3 . Sea T una familia de grafos . La funci ó n ex { y \ T ) representa al m á ximo n ú mero de aristas que puede tener un grafo con V v é rtices sin contener a ning ú n grafo de T como subgrafo . Por tanto , todo grafo de orden V y tama ñ o ex [ v \ T ) 1 ب contiene algUn F T como subgrafo . Los grafos de orden V y tama ñ o ex { v % ) T ) que no contienen a ning ú n F e T como subgrafo son los grafos extremales , denotados por EX [ y \ T ) . La funci ó n extremal que vamos a considerar es ex { i / \ { G 3 , G 4 , ٠ . ٠ , C ] representa el m á ximo n ú mero de aristas de un grafo simple con V v é rtices y cintura al menos ft + 1 . Los grafos extremales del problema forman la familia EX ( v \ { G 3 , G 4 , ٠٠٠ , G , , que © This research was supported by the Ministry of Education and Science , Spain , and the European Regional Development Fund ( ERDF ) under project MTM 2005 - 08990 - C 02 - 02 . 18 El tama ñ o de un grafo con cintura interiormente acotada ت | y / 4 _ | y la familia El caso ft = 3 es bien conocido : la funci ó n ex ( ¡ / • ) { C 3 extremal EX ( ] / ‘ ) { C 3 } ) = { K [ v / 2 ا 2 / ر ٤٢ , ل } • Por tanto , a lo largo de este trabajo consideramos que ft > 4 . El caso ft = 4 ha sido estudiado en [ 2 ] y [ 3 ] . En el primer trabajo se proporciona el valor exacto de ex ( ¡ / • ) { C $ ) Ci } ) para todo z , 24 y se acota interiormente dicha funci ó n para los valores de i , 200 . En [ 3 ] se obtienen los valores exactos para 25 ^ 30 . En [ 4 ] se prueba que ex { 2 n + 2 ; { C 3 , c ، 4 , .. . , Cn } ) = 2 n 4 ب para ^ ' 12 y los autores afirman que creen tener un resultado similar al anterior para el caso V = 3 ft 3 ب cuya demostraci ó n es larga y dif í cil . Hasta el momento no se conoce ning ú n otro valor exacto de la funci ó n extremal ex ( ¿ ; ; { C 3 , C 4 , ... , Cn } ) ‘ Debido a la dificultad de hallar los valores exactos de esta funci ó n , algunos au - tores han buscado propiedades generales que deben cumplir los grafos extremales . En este contexto , los autores del trabajo [ 4 ] sugieren : ¿ cu á l es la cintura de un grafo extremal de orden V y libre de ciclos { C 3 , C 4 , ... , Cn } ? ¿ Es siempre n + 1 0 puede ser mayor ? Este problema ha sido estudiado en [ 2 , 3 , 4 ] . A continuaci ó n mostramos los resultados m á s relevantes : ( 3 , 2 ] ( ؛ ] Para z , 7 , la cintura de un grafo extremal libre de { C 3 , C 4 } es 5 . ( n ) [ 4 ] Para z , 8 , la cintura de un grafo extremal libre de { C 3 , Ci ) C 5 } es 6 . ( iii ) [ 4 ] La cintura de un grafo extremal libre de { ﻰﯨﺑ , . . . , 4 ى , 3 ى y m á xima valencia A > nesn + 1 . ( ‘ iv ) [ 4 ] Sea G ج EX ( ] / ) { C 3 , C 4 , . . . , Cn } ) con ft > 12 , a : n — 3 — | ( ft - 2 ) / 4 ل y > 2 ﺄھ 7 ل + ﺐﻋ 2 ه . Entonces la cintura g ( G ) = ft + l . En [ 4 ] tambi é n se plantea el siguiente problema : Sea gmax ( n ) la m á xima cintura de los grafos de EX ( ¡ / ' ) { C 3 , C 4 , ... , cn } ) para todo V . ¿ Cu á l es el mayor valor de la diferencia gmax ( n ) — ( n + 1 ) ? Considerando los resultados anteriormente expuestos , pretendemos determi - nar los valores exactos de la funci ó n extremal y las posibles cinturas de los grafos extremales . Para ello analizamos los posibles valores que puede tomar la funci ó n ex ( ¿ ; ; { C 3 , C 4 , ... , cn } ) — V ) es decir , la diferencia entre el tama ñ o y el orden de un grafo extremal . Analizando dichos valores hemos podido obtener el valor exacto de ex ( ¿ ; ; { C 3 , C 4 , . . . , cn } ) para V ل 5 / ( 5 ا — ^ 16 ) ؛ y para todo 4 . La pregunta sugerida en [ 4 ] acerca de gmax ( n ) queda resuelta en el Teorema 5 . Resulta mucho m á s interesante reformularla en los siguientes t é rminos : conside - remos n > 4 , V > n 1 ب , si por gmax ( ri ) V ) denotamos la cintura m á xima de los grafos de EX ( ¡ / • ) { C 3 , Ci ) . . . , cn } ) \ ¿ cu á nto vale gmax ( n ) ¡ y ) ? El Teorema 4 responde a esta cuesti ó n para V L ( 1 - 15 ) / 5 ل . V 19 E . Abajo , A . Di á nez Es evidente , que encontrar los grafos extremales del problema planteado es una tarea bastante complicada pero el Teorema 1 afirma que los grafos extremales son , bajo ciertas condiciones , muy similares unos a otros , en el sentido de que se obtienen a ñ adiendo v é rtices de valencia 1 y / o subdividiendo aristas de algUn grafo 0 multigrafo hasta obtener la cintura deseada , como puede observarse en la Figura 2 . Este resultado nos sugiere que el conocimiento de alg ú n grafo extremal para ft peque ñ o puede aportar una cota inferior , mediante la subdivisi ó n de aristas , para otros valores de ft . Como veremos en el Ejemplo 1 a partir del grafo de Petersen , extremal para ft = 4 , se pueden construir grafos de EX ( 3 n - 2 ; { Cs , C \ ) ٠ . . , C , para ft 4 . Por ello , en la segunda parte del trabajo nos centramos en el estudio de la funci ó n extremal para ft = 5 , 6 , 7 . 2 RESULTADOS GENERALES Es obvio que ex { v + l ' , { Czy . . , Cn } ) ex ( z , ; { C ] y .. , Cn } ) + 1 , es decir , la funci ó n ex ( z , ; { C 3 , C 4 , . ٠ . , Cn } ) es estrictamente creciente . Consideremos la di - ferencia entre el tamafio y el orden de los grafos de EX { v \ { C 3 , C 4 , . . . , Cn } ) , es decir , ex { v ; { C 3 , C 4 , .. . , Cn } ) - V . Se trata de una funci ó n que toma valores en - teros positivos , es creciente pero no estrictamente . Nuestro objetivo es determinar los valores de V para los que la funci ó n permanece constante . Por comodidad , denotamos por Ek a la familia de grafos , multigrafos y pseu - dografos H que verifican e { H ) - v { H ) = k y 6 { H ) 3 . Es obvio que Ek es una familia finita para cada k . Definici ó n 1 . Sean n > 4 y k > 0 enteros . Se define Uk ، on ١ = m Í Ti \ y * ١ exVv * ١ \ C ^ ١ C 4١ . . . ١ c ٦ k } — y : El par á metro y ^ ( ft ) no siempre existe . Por ejemplo , en [ 2 ] , se prueba que = 15 . Por tanto , no existe 2 , 4 ( 4 ) . Pero , = 12 yex ( 10 ; { C 3 , C 4 ex ( 9 ; { C 3 , C 4 podemos afirmar : 2 k 4 - 2 ١١ ) existe y tal que : k > 0 entero . Para cada ft ) 2 log 2 ( Teorema 1 . Sea 3 ( i ) exVy ٠ AC * ١ C 4١.٠٠١ C ١ ( ii ) Todo grajo de EX ؛ y - ؛ ١ C ^ ١ C 4١ . . . ١ c ٦ : y tiene valencia minima a lo sumo ، 1 . ( iii ) Todo grajo de EX ^ y ١ ( C ^ ٩ C 4١ ... ١ C ٦ se obtiene afiadiendo r é rtiees de ralenciaL g / o sudiridiendo las aristas de grajos 0 multigrajos de Sk El tama ñ o de un grafo con cintura interiormente acotada 20 Este resultado conlleva que parte del estudio de los gratos extremales puede ser reconducido a determinar los gratos y multigrafos de Sk ) una cantidad finita para cada k ) que son el resultado de sustituir cada camino formado por v é rtices de valencia 2 en el grafo extremal por una nueva arista y eliminar los caminos formados por v é rtices de valencia 2 cuyo final es un v é rtice de valencia 1 . Abordando los primeros valores k posibles de ex ( V ) { C ? t ) Ci ) ... ) C hemos obtenido : — V ) n V 36 32 28 24 20 16 12 4 - n 6 ؟ ٠ 4 9 10 11 12 Fig . 1 : Valores exactos de la funci ó n ex ( is - ) { C 3 , Ci ) . ٠٠ , c n Teorema 2 . Sea ft 4 entero . Entonces : ٠١٢ = ١١ أ 4١ ، ٢ } ا ( il ) jq ( ft ) = L 3 ft / 2 J 4 1 ( iii ) V 2 ( 12 ) = 2 ft { 9٢ ft / 4 SX n es par si , n es impar = ( ) 3 ¿ ( يﺄﺑ ) 4 / 9 ft ؛ E . Abajo , A . Di á nez 21 ًا r ( 8 n — 2 ) / 3٦ si n 4 ﻢﻟ es par L ( 8 n - 2 ) / 3 ل si n es impar ( V ) V \ ( n ) = ًا if n ﺐﺗ 7 71 = 6 3 n — 2 3 ^ — 1 ( vi ) 5 ًار ( n ) = 12 = ( 4 ) 1 / 6 دار , e ( 5 ) = 14 ) g ( 6 ) = 19 , 1 / 6 ( 7 ) = 21 , ٢ ( 1 — 5 ) / 3٦ L ( 10 rc - 6 ) / 3 j { si n > 8 es par si n > § es impar > ( ا 7 ) 6 ﺔﻤھ > 5٦ / ( 14 - 1 ) ٢ Los valores iSk ( n ) anteriormente determinados junto con el Teorema 3 propor - cionan el valor exacto de ex ( z / ; { C 3 , C 4 , Cn } ) para cada ﺔﻤھ < L ( 16 n — 15 ) / 5 ل y para cada n > 4 ( ver Figura 1 . ) < i / k + i ( n ) , entonces Teorema 3 . Sean n > 4 y k > 0 enteros . Si Uk ( n ) ex { y \ { C ] ) C \ ) ... ) C ] Los resultados obtenidos en los Teoremas 2 y 3 nos permiten determinar todas las posibles cinturas de los grafos extremales para ﺔﻤھ L ( 1 - 15 ) / 5 J , como muestra el siguiente resultado : Teorema 4 . Sean n > 4 y ﺔﻤھ > n 1 ب enteros y denotemos por ، 7 max ( n , ﺔﻤھ ) la maxima cintura de los grajos de EX ( y * ١ \ 0٩ ... ١40٩ ﻵ c ٦ i ) 9 max { ji , v ) toma los siguientes valores : . Entonces ( ﺔﻤھ , max ( n ? ، ( n ) ﺔﻤھا > ﺔﻤھ > ( 0 ( n ﺔﻤھ L ( 2 í / - f 2 ) / 3 ل ( n ) ^ > ﺔﻤھ > ( n ) ﺔﻤھا ل 2 / ( 2 + س ٤ ( س 3 ﻢھ ٤ > ﺔﻤھ ( 2٧ { n L ( 4 ، / | 12 ) / 9 J 9 / ( 2 + ا ، 4 ) 9 8 mod ﻢﻟ ﻢھ 2٤ ؛ 5 9 8 mod = ﻢھ 2٤ ؛ 5 ( 71 ) 1 / 4 > ﻢھ ٤ ( ى 3 ﻢھ ٤ ل 8 / ( 12 + ﻢھ 3٤ ) ؛ ل 8 / ( 4 + ﻢھ 3٤ ) ؛ 16 12 , 13 mod ﻢﻟ ﺔﻤھ 3 si 16 12 , 13 mod = ﻢھ 3٤ ؛ 5 ( أ 7 ) ةﺮﺟ > ﺔﻤھ > ( 77 ) 4 / ، ﻖﻟ / ( 5 ب / ، ) L 5 ًار ( n ) í , < i / 6 ( n ) ü ) Para todo ٦ e \ u 1 ٢ د , gti ( n ١ v ١ \ es posible construir i grajo G de EX { v \ { c ، 3 , Cn } ) ، « ًا que g { G ) = 7 . 22 El tama ñ o de un grafo con cintura interiormente acotada Obs é rvese que la funci ó n gmax { n , is ) estudiada en el Teorema 4 es una ex - tensi ó n de ، 7 max ( n ) , introducida en el articulo [ 4 ] , en el que los autores se pre - guntan sobre el valor m á ximo de la cintura de todo grafo extremal independien - temente de su orden . Esta cuesti ó n queda resuelta en el siguiente teorema , la m á xima cintura es | 3 n / 2 j . Teorema 5 . Sea n > 4 entero . 9 max ( n ) = max ى ) ًﺎھ ) ; G ج EX { ¡ / { ل 3 ء Cir ٠٠ , C , ( + 2 ع n / 2 ل عر , 3 LA FUNCI ó N EXTREMAL PARA n = 5 , 6 , 7 Como comentamos en la introducci ó n se conocen muy pocos valores exactos de la funci ó n extremal . De hecho , todos los trabajos se centran en n = 4 . El Ultimo articulo publicado sobre este tema [ 5 ] es del a ñ o 2001 , donde los autores implementan un algoritmo que construye grafos con cintura al menos 5 , que proporcionan una cota inferior de la funci ó n extremal ex ( ، / ; { C 3 , C 4 } ) que resulta ser ó ptima para los casos conocidos con z , 29 . Siguiendo esta linea de fijar el valor de n en la funci ó n extremal , nuestro siguiente objetivo es abordar los casos n = 5 , 6 , 7 . Es inmediato generalizar la conocida cota inferior ( ver [ 1 ] , pag 308 ) del nUmero de v é rtices de los grafos regulares con cintura dada . Asi , si G es un grafo con cintura g ( G ) > n y valencias m á xima y minima ح y د , respectivamente , tiene el orden interiormente acotado por : ñ ا - ، ( ا - ى ) ﺢﺣ SI n es par I / ( G ) ( ا - ي ) + ل - ، ( 1 - ي ) ﺢﻋ n — SI n es impar Apoy á ndonos en esta cota y en varios lemas t é cnicos que permiten controlar las valencias de los v é rtices de los grafos extremales , hemos obtenido algunos valores exactos de la funci ó n extremal que aparecen reflejados en el siguiente resultado : E . Abajo , A . Di á nez 23 Teorema 6 . La funci ó n extremal ex ( i / ' , { Cb ٠ .. , C \ res : toma los stg ^ te ^ tes ralo - n ٠ Si n ت b 0 2 3 4 5 6 8 9 V 0 2 3 1 4 6 7 9 10 10 12 14 16 18 21 22 24 26 29 31 20 34 36 39 42 45 48 52 53 56 ا ؟ : Si n ٠ 0 2 3 5 4 6 7 8 9 ار 0 ة 1 3 4 5 7 8 9 12 10 11 14 15 17 18 20 22 23 25 20 27 29 31 33 36 37 39 41 43 ٠ Sin 7 ت 0 2 3 4 5 6 8 9 V 2 3 4 0 5 6 8 9 10 10 12 13 14 16 18 19 20 22 24 20 25 27 29 30 32 34 36 38 40 42 30 45 46 La demostraci ó n del teorema anterior es constructiva en el sentido de que para cada w = 5 , 6 , 7 y cada V se construye un grafo de EX { v \ { C 3 , .. . , Cn } ) . Las subdivisiones de sus aristas , seg ú n el Teorema 1 , proporcionan posiblemente grafos extremales para otros valores de n 0 al menos grafos que constituyen una cota inferior de la funci ó n extremal , como ilustramos a continuaci ó n : E ‘ ^ emp \ o L . El grajo de Petersen es un grajo de orden tamano Ib ﻷ extremal para ex ( v \ ؟ y ٦ \ C ^ AY ) ( ver [ 2 ] ) . La subdivisiones de las aristas tal ( como se muestra en la Figura 2 proporcionan grajos extremales para todo n ح ^ de la Junci ó n ex 2 ; { C 3 , . . . , ç n n 24 El tama ñ o de un grafo con cintura interiormente acotada . . . l ( n - 2 ) / s ) ا 5 ا ( 3 - " ) إ - 1 ( ) n - 4 ) / 5 Fig . 2 : Gratos de EX { 3 n - 2 ; { C 3 , ٥١٠٠٠ , 4 PROBLEMAS ABIERTOS Las cuestiones pendientes en el estudio de la funci ó n extremal ex ( y \ { C 3 , Cn } ) son numerosas y muy complicadas . Seria interesante hallar el valor exacto de continuar abordando valores concretos den = 8 , 9 , ... , caracterizar los gratos y multigrafos cuyas subdivisiones proporcionan gratos extremales , . ٠ . Pero nuestro primer objetivo es responder a la cuesti ó n sobre la cin - tura de los gratos extremales . En [ 4 ] se prueban dos resultados , bajo hip ó tesis muy restrictivas , que garantizan que la cintura de los grafo de EX [ y \ { C 3 , ... , Cn ) ) es 71 + 1 . Actualmente , estamos tratando de rebajar dichas hip ó tesis . REFERENCIAS [ 1 ] Chartrand , G . y Lesniak , L . Graphs and Digraphs , Third edition . Chapman and Hall , London , UK ( 1996 ) . [ 2 ] Garnick , D . K . , Kwong , Y . H . H . y LazebnikjF . Extremal graphs without three - cycles or four - cycles , 3 . Graph Theory 17 ( 1993 ) , 633 - 645 . [ 3 ] Garnick , D . K . y Nieuwejaar , N . A . Non - isomorphic extremal graphs without three - cycles or four - cycles , JCMCC 12 ( 1992 ) , 33 - 56 . [ 4 ] Lazebnik , F . y Wang p . On the estructure of extremal graphs of high girth , 3 . Graph Theory 26 ( 1997 ) , 147 - 153 . [ 5 ] Wang , P . , Dueck , G . w . y MacMillan , s . Using simulated annealing to consti ' uct extremal graphs . Discrete Mathematics 235 ( 2001 ) , 125 - 135 .