Uno de los problemas que se investigó como parte de este trabajo, fue el caracterizar las gráficas G que maximizan a |K 2 (G)|. Los resultados obtenidos sobre este problema, se describen a detalle en el capítulo 2 y se publicaron en [52] y en [53]. Si bien, el problema continúa abierto, los experimentos computacionales nos han llevado a conjeturar que si G es una gráfica de n vértices, entonces |K 2 (G)| está acotado por los siguientes valores (conjetura 2.36): |K 2 (G)| ⩽ √ 2 √ 2 n , si n es par, √ 5 √ 2 n−3 , si n es impar. También conjeturamos que las cotas superiores se alcanzan con la gráfica Gn, dada por (definición 2.3): Gn = O n 2 , si n es par, O n−3 2 + I3, si n es impar. Si la conjetura fuera cierta, entonces Gn es una suspensión S(H), de una gráfica H, esto es: Gn = S(H) = I2 + H. Es por ello que para estudiar las gráficas que maximizan a |K 2 (G)|, se propuso un nuevo operador de biclanes B(G) (definición 2.5), con el cual se caracterizó la segunda gráfica iterada de clanes de suspensiones de G, en términos de B(G), esto es: B(G) = K 2 (S(G)) (teorema 2.8). También se caracterizaron las gráficas G que maximizan a |B(G)| y se demostró que esto ocurre precisamente cuando G = Gn, lo que sugiere que la conjetura 2.36, podría ser cierta. En la sección 2.3, presentamos resultados y una estrategia general, que podrían ser útiles para demostrar la conjetura 2.36. Otro de los problemas que se investigó en este trabajo, fue el determinar si existe una gráfica G, para la que el orden de sus gráficas iteradas de clanes tiene crecimiento exponencial, esto es: |K n(G)| = Θ(a n), con a > 1. Este problema lleva a su vez a la cuestión de encontrar una gráfica G, que al menos muestre dicho comportamiento en experimentos computacionales y de esta forma pueda servir como punto de partida de la investigación. Por las razones que se exponen a detalle en el capítulo 3, no es computacionalmente factible revisar cada gráfica del conjunto de gráficas de n vértices para buscar a la gráfica G de interés, es por ello que se requiere una búsque da más dirigida. Para los fines de esta investigación, una heurística basada en algoritmos genéticos arrojó resultados satisfactorios. Los principios generales de un algoritmo genético, así como la implementación que se usó en este trabajo, se describen con extenso detalle en el capítulo 3. Mediante dicha heurística se encontró que la gráfica circulante G = Cn(1, 3, 6, 7, 8), con n ⩾ 25, experimentalmente tiene crecimiento exponencial. Para estudiar las propiedades de las gráficas K i (Cn(1, 3, 6, 7, 8)), en el capítulo 4, se define una familia de gráficas que hemos denominado gráficas bobina generalizadas. Las cuales son una generalización de las gráficas bobina definidas por Larrión, Pizaña y Villarroel-Flores, en [42]. En particular, cualquier gráfica circulante que cumple las condiciones del lema 4.3 (como lo es la gráfica Cn(1, 3, 6, 7, 8)), es una gráfica bobina generalizada. Si G es una gráfica bobina generalizada, en la sección 4.2, se demuestra que K(G) también es una gráfica bobina generalizada (teorema 4.7). Entre otros resultados, también se dan caracterizaciones de las adyacencias de G, en términos de sus clanes (lema 4.12) y se dan lemas para obtener subgráficas completas de K(G). Tenemos la conjetura de que G = Cn(1, 3, 6, 7, 8), con n ≥ 25, cumple que |K i (G)| = 3 · |K i−2 (G)| + |G|, para i ≥ 2 (conjetura 3.12). De ser cierta dicha conjetura, en la sección 3.5 se muestra que esto implicaría que |K i (G)| = Θ(3 n 2 ) (teorema 3.15).
Beziehungen
Beschreibungen
| Attributname | Werte |
|---|
| Creador |
|
|---|
| Mitwirkende |
|
|---|
| Tema |
|
|---|
| Editor |
|
|---|
| Idioma |
|
|---|
| Identificador |
|
|---|
| Stichwort |
|
|---|
| Año de publicación |
|
|---|
| Tipo de Recurso |
|
|---|
| Derechos |
|
|---|
| División académica |
|
|---|
| Línea académica |
|
|---|
| Licencia |
|
|---|
