Liczby Ramseya on-line dla różnych klas grafów - Publikacja - MOST Wiedzy

Wyszukiwarka

Liczby Ramseya on-line dla różnych klas grafów

Abstrakt

Rozpatrujemy grę rozgrywaną na nieskończonej liczbie wierzchołków, w której każda runda polega na wskazaniu krawędzi przez jednego gracza - Budowniczego oraz pokolorowaniu jej przez drugiego gracza - Malarkę na jeden z dwóch kolorów, czerwony lub niebieski. Celem Budowniczego jest zmuszenie Malarki do stworzenia monochromatycznej kopii wcześniej ustalonego grafu H w jak najmniejszej możliwej liczbie ruchów. Zakładamy, że gracze grają optymalnie czyli najlepiej jak można w danym momencie i nie popełniają błędów. Malarka będzie próbowała przeszkodzić Budowniczemu jak długo się tylko da. Taką grę będziemy nazywać ̃(H)-grą. W wersji asymetrycznej tej gry, Malarka unika czerwonej kopii grafu G oraz niebieskiej kopii grafu H. Taką grę będziemy nazywać ̃ (G, H)-grą. Wartością liczby Ramseya on-line ̃(H) - wersja symetryczna lub ̃(G, H) - wersja asymetryczna, jest to minimalna liczba tur, w której gra się zakończy. W rozprawie rozważamy liczby Ramseya on-line dla różnych klas grafów. Wyznaczamy wartości liczb Ramseya on-line ̃(P4, P10), ̃(P4, P11) oraz górne oszacowanie ̃(P4, Pn) dla 12 ≤ n ≤ 22. Ponadto przedstawiamy górne oszacowanie ̃(S3, Pl) dla l ≥ 3 oraz dokładną wartość ෩(S3, P5). Pokazujemy nowe oszacowania z dołu i góry dla liczb ̃(C3, Pk) oraz ̃(C4, Pk) dla odpowiednich k oraz wyznaczamy dokładną wartość ̃(C4, P9).

Cytuj jako

Pełna treść

pobierz publikację
pobrano 49 razy
Wersja publikacji
Accepted albo Published Version
Licencja
Copyright (Author(s))

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Doktoraty, rozprawy habilitacyjne, nostryfikacje
Typ:
praca doktorska pracowników zatrudnionych w PG oraz studentów studium doktoranckiego
Język:
polski
Rok wydania:
2023
Weryfikacja:
Politechnika Gdańska

wyświetlono 48 razy

Publikacje, które mogą cię zainteresować

Meta Tagi