| UN ETIQUETAMIENTO DE UN GRAFO ES UNA FUNCION DE LOS VERTICES (O DE LAS ARISTAS) DEL GRAFO A UN SUBCONJUNTO DE LOS NUMEROS NATURALES. EN ESTA TESIS ESTUDIAMOS DOS TIPOS DE ETIQUETAMIENTOS DE ARISTAS: LOS FLUJOS NO NULOS Y LOS ETIQUETAMIENTOS DE ARISTAS INDUCIDOS POR ETIQUETAMIENTOS DE VERTICES. ADICIONALMENTE, ESTUDIAMOS UN PROBLEMA DE RECONSTRUCCION DE GRAFOS A PARTIR DE UN POLINOMIO DEL GRAFO. ES CONOCIDA LA CARACTERIZACION DE LOS GRAFOS CUBICOS QUE TIENEN UN 4-FLUJO NO-NULO. ESTA CARACTERIZACION SE BASA EN LA EXISTENCIA DE UN 3-COLOREAMIENTO DE LAS ARISTAS. EN ESTA TESIS EXTENDEMOS ESTOS RESULTADOS DANDO UNA CARACTERIZACION DE LOS GRAFOS CUBICOS QUE TIENEN UN 5-FLUJO NO-NULO. ESTA CARACTERIZACION SE BASA EN LA EXISTENCIA DE UN TIPO ESPECIAL DE FACTOR DEL GRAFO QUE HEMOS LLAMADO UN (1,2) FACTOR PAR. PARA TODO GRAFO UN ETIQUETAMIENTO DE VERTICES INDUCE UN ETIQUETAMIENTO DE ARISTAS QUE ASIGNA A CADA ARISTA EL VALOR ABSOLUTO DE LA DIFERENCIA DE LOS VALORES DE SUS EXTREMOS. SEGUN LAS CARACTERISTICAS DEL ETIQUETADO INDUCIDO (INYECTIVIDAD, CONJUNTO IMAGEN, CUMPLIMIENTO DE UNA ECUACION, ETC.) PODERMOS DIVIDIR LOS ETIQUETAMIENTOS DE VERTICES DE UN GRAFO EN DISTINTAS FAMILIAS. DADOS UN GRAFO G, UN SUBCONJUNTO B N Y UNA FAMILIA DE ETIQUETAMIENTOS F, ESTUDIAMOS LA EXISTENCIA DE UN ETIQUETAMIENTO DE G EN F QUE TENGA COMO IMAGEN EL CONJUNTO B. EN PARTICULAR, PROBAMOS LA EXISTENCIA DE FAMILIAS DE GRAFOS Y FAMILIAS DE ETIQUETAMIENTOS, TAL QUE PARA TODO GRAFO DE LA FAMILIA SIEMPRE EXISTE UN ETIQUETAMIENTO DE LA FAMILIA INDEPENDIENTE DEL CONJUNTO IMAGEN. A CONTINUACION, ESTUDIAMOS DOS FAMILIAS PARTICULARES DE ETIQUETAMIENTOS. POR UN LADO ESTUDIAMOS LOS ETIQUETAMIENTOS DE VERTICES QUE INDUCEN UN ARISTA COLOREAMIENTO DEL GRAFO. EN ESTE CASO PROBAMOS QUE TODOS LOS GRAFOS TIENEN UN ETIQUETAMIENTO DE ESTE TIPO CON CONJUNTO IMAGEN B, CUYO ELEMENTO MAXIMAL ES A LO MAS NLOG23, DONDE N ES EL NUMERO DE VERTICES DEL GRAFO. PARAñoBTENER ESTA COTA CONSTRUIMOS ETIQUETADOS PARA LOS GRAFOS MULTIPARTITOS DE MANERA INDUCTIVA. POR OTRO LADO, ESTUDIAMOS LOS ETIQUETAMIENTOS DE DISTANCIAS. CARACTERIZAMOS LAS SECUENCIAS DE GRADO DE LOS GRAFOS QUE TIENEN UN ETIQUETAMIENTO DE DISTANCIA CUYA IMAGEN ES EL CONJUNTO {0,1,...,N - 1}. FINALMENTE, ESTUDIAMOS EL PROBLEMA DE RECOSNTRUCCION DE GRAFOS DESDE SU U-POLINOMIO. EN ESTA TESIS NOS CONCENTRAMOS EN EL PROBLEMA PARA LA FAMILIA DE ARBOLES CONOCIDA COMO LAS CUNCUNAS. PROBAMOS QUE EL POLINOMIO OBTENIDO DESDE EL U-POLINOMIO SACANDO LOS TERMINOS CON LA INDETERMINADA X1 NO ES SUFICIENTE PARA RECONSTRUIR CUNCUNAS. PARA HACER ESTO REINTERPRETAMOS EL PROBLEMA DE RECONSTRUCCION DE CUNCUNAS A PARTIR DE ESTE POLINOMIO, COMO UNA RECONSTRUCCION DE SECUENCIAS NUMERICAS A PARTIR DE SUS SUMAS PARCIALES. |