Graphs with every path of length k in a hamiltonian cycle

Typ: Artykuł

Liczba pobrań: 555

Pobierz zasób

PDF

Cytuj

Tytuł: 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