Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
Ciclos hamiltonianos que pasan a través de un bosque lineal en grafos bipartitos balanceados
PDF

Palabras clave

bipartite graph
linear forest
hamiltonian cycle
grafo bipartito
bosque lineal
ciclo hamiltoniano

Cómo citar

Brito, D., Marín, L., & Ramírez, H. (2018). Ciclos hamiltonianos que pasan a través de un bosque lineal en grafos bipartitos balanceados. Revista De Matemática: Teoría Y Aplicaciones, 25(2), 347–365. https://doi.org/10.15517/rmta.v25i2.33908

Resumen

Sea G = (A B, E) un grafo bipartito con |A| = |B| = n ≥ 4. Un grafo es un bosque lineal si cada componente es un camino. Sea S un conjunto de m lados de G que induce un bosque lineal. Probaremos que si σ1,1(G) = min{dG(u) + dG(v) : uA, vB, uv ̸∈ E(G)} ≥ (n+1)+m, entonces G contiene (m+1) ciclos hamiltonianos Cj tal que |E(Cj ) ∩ S| = j, con j = 0, 1, . . . , m.

https://doi.org/10.15517/rmta.v25i2.33908
PDF

Citas

Chen, G.; Enomoto, H.; Lou, D.; Saito, A. (2001) “Vertex-disjoint cycles containing specified edges in a bipartite graph”, Australasian Journal of Combinatorics 23(1): 37–48.

Diestel, R. (2000) Graph Theory. Springer-Verlag, New York.

Posa, L. (1963) “On the circuits of finite graphs (russian summary)”, Magyar Tud. Akad. Mat. Kutató Int. Köz 8(1): 355–361.

Sugiyama, T. (2004) “Hamiltonian cycles through a linear forest”, SUT Journal of Mathematics 40(2): 103–109.

Wang, H. (1999) “Covering a bipartite graph with cycles passing through given edges”, Australasian Journal of Combinatorics 19(1): 115–121.

Comentarios

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.

Derechos de autor 2018 Daniel Brito, Lope Marín, Henry Ramírez

Descargas

Los datos de descargas todavía no están disponibles.