Árboles generadores con sucesiones de grado dada Público Deposited
Un árbol generador T de una gráfica G es una subgráfica de G tal que T es un árbol y el conjunto de vértices del árbol T es igual al conjunto de vértices de G. En este trabajo damos una condición necesaria y una condición suficiente para que una gráfica simple tenga al menos un árbol generador con sucesión de grados preestablecida. También demostramos que el problema de decidir si una gráfica tiene un árbol generador con cierta sucesión de grados es NP-completo. Definimos una transformación φ, basada en la Operación de Adopción dada por Fekete et al. [9], que convierte un árbol generador T de una gráfica simple G en cualquier otro árbol generador de G cuya sucesión de grados es una permutación de la sucesión de grados de G. Dado un árbol T con sucesión de grados σ definimos una gráfica Gπ(σ) cuyos vértices son todos los árboles que tienen como sucesión de grados a una permutación de σ y en la cual dos ´arboles R y S son adyacentes si uno se obtiene del otro usando la transformación φ. Demostramos que para toda sucesión arbórea σ, la gráfica Gπ(σ) es conexa y damos dos algoritmos que encuentran una trayectoria entre cualquier par de vértices de una gráfica Gπ(σ) . Finalmente, usando nuestros algoritmos, acotamos el diámetro de las gráficas Gπ(σ).
Relaciones
| En Conjunto Administrativo: |
|---|
Descripciones
| Nombre del atributo | Valores |
|---|---|
| Creador | |
| Colaboradores | |
| Tema | |
| Editor | |
| Idioma | |
| Palabra Clave | |
| Año de publicación |
|
| Tipo de Recurso | |
| Derechos | |
| División académica | |
| Línea académica | |
| Licencia |
