Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "k-traceable" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-2 z 2
    Tytuł:
    Every 8-Traceable Oriented Graph Is Traceable
    Autorzy:
    Aardt, Susan A. van
    Powiązania:
    https://bibliotekanauki.pl/articles/31341593.pdf
    Data publikacji:
    2017-11-27
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    oriented graph
    traceable
    hypotraceable
    k-traceable
    generalized tournament
    Opis:
    A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8-traceable oriented graph is traceable.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 4; 963-973
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture
    Autorzy:
    de Wet, Johan P.
    Frick, Marietjie
    Powiązania:
    https://bibliotekanauki.pl/articles/32222536.pdf
    Data publikacji:
    2022-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    locally traceable
    locally hamiltonian
    Hamilton Cycle Problem
    locally k -nested-hamiltonian
    Oberly-Sumner Conjecture
    Opis:
    A graph G is locally P, abbreviated L, if for every vertex v in G the open neighbourhood N(v) of v is non-empty and induces a graph with property P. Specifically, a graph G without isolated vertices is locally connected (LC) if N(v) induces a connected graph for each v ∈ V (G), and locally hamiltonian (LH) if N(v) induces a hamiltonian graph for each v ∈ V (G). A graph G is locally locally P (abbreviated L2P) if N(v) is non-empty and induces a locally P graph for every v ∈ V (G). This concept is generalized to an arbitrary degree of nesting. For any k ≥ 0 we call a graph locally k-nested-hamiltonian if it is LmC for m = 0, 1, . . ., k and LkH (with L0C and L0H meaning connected and hamiltonian, respectively). The class of locally k-nested-hamiltonian graphs contains important subclasses. For example, Skupień had already observed in 1963 that the class of connected LH graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any k ≥ 1 the class of locally k-nested-hamiltonian graphs contains all simple-clique (k + 2)-trees. In 1979 Oberly and Sumner proved that every connected K1,3-free graph that is locally connected is hamiltonian. They conjectured that for k ≥ 1, every connected K1,k+3-free graph that is locally (k + 1)-connected is hamiltonian. We show that locally k-nested-hamiltonian graphs are locally (k + 1)-connected and consider the weaker conjecture that every K1,k+3-free graph that is locally k-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be “best possible” in the sense that for every k ≥ 1 there exist K1,k+4-free locally k-nested-hamiltonian graphs that are non-hamiltonian. We also attempt to determine the minimum order of non-hamiltonian locally k-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally k-nested-hamiltonian graphs with restricted maximum degree.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1281-1312
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-2 z 2

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies