Graphs with every path of length k in a hamiltonian cycle
Wariant tytułu
Grafy z dowolną ścieżką długości k zawartą w pewnym cyklu hamiltonowskim
Autor
Gancarzewicz, Grzegorz
Opublikowane w
Technical Transactions
Numeracja
Y. 111, iss. 2-NP
Strony
45-58
Data wydania
2014
Miejsce wydania
Kraków
Wydawca
Wydawnictwo PK
Język
angielski
Słowa kluczowe
cycle, graph, hamiltonian cycle, matching, path
cykl, cykl hamiltonowski, graf, skojarzenie, ścieżka
Abstrakt
In this paper we prove that if G is a (k+2)-connected graph on n≥3 vertices satisfying P(n+k) :
dG(x, y) = 2⇒max {d(x), d(y)g}≥ n+k⁄2 for each pair of vertices x and y in G, then any path S⊂G of length k is contained in a hamiltonian cycle of G.
W pracy udowodniono, ze W (k+2)-spójnym grafie G o n≥3 wierzchołkach, który spełnia warunek P(n+k) :
dG(x, y) = 2⇒max {d(x), d(y)g}≥ n+k⁄2 dla dowolnej pary wierzchołków x i y; każda ścieżka S⊂G długości k jest zawarta w pewnym cyklu hamiltonowskim grafu G.
Wydział
Wydział Fizyki, Matematyki i Informatyki
Licencja
Licencja PK
Prawa dostępu
Zasób dostępny dla wszystkich
Na stronie wykorzystywane są pliki cookie, bądź podobne rozwiązania. Aby poznać szczegóły zapoznaj się z polityką prywatności.