Ciclos hamiltonianos que pasan a través de un bosque lineal en grafos bipartitos balanceados

• Autores: Daniel Brito, Lope Marín, Henry Ramírez
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 25, Nº. 2, 2018, págs. 349-367
• Idioma: español
• DOI: 10.15517/rmta.v25i2.33908
• Títulos paralelos:
  • Hamiltonian cycles that pass through of a linear forest in bipartitos grafos balanced
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    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) : u ∈ A, v ∈ B, uv 6∈ E(G)} ≥ (n+1)+m, entonces G contiene (m+1) ciclos hamiltonianos Cj tal que |E(Cj ) ∩ S| = j, con j = 0, 1, . . . ,m.

  • English

    Let G = (A ∪ B,E) be a bipartite graph whith |A| = |B| = n ≥ 4. A graph is linear forest if every component is a path. Let S be a set of medges of G that induces a linear forest. We prove that ifσ1,1(G) = min{dG(u) + dG(v) : u ∈ A, v ∈ B, uv 6∈ E(G)} ≥ (n + 1) + m, then G contains (m + 1) hamiltonian cycles Cj such that |E(Cj ) ∩ S| = j, with j = 0, 1, . . . ,m.

• Referencias bibliográficas
  • Chen, G.; Enomoto, H.; Lou, D.; Saito, A. (2001) “Vertex-disjoint cycles containing specified edges in a bipartite graph”, Australasian Journal...
  • 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.