Autor: Offner, David - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Packing the Hypercube
Autorzy:: Offner, David
Powiązania:: https://bibliotekanauki.pl/articles/30147221.pdf
Data publikacji:: 2014-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hypercube
packing
decomposition
Opis:: Let G be a graph that is a subgraph of some n-dimensional hypercube Q_n. For sufficiently large n, Stout [20] proved that it is possible to pack vertex-disjoint copies of G in Q_n so that any proportion r < 1 of the vertices of Q_n are covered by the packing. We prove an analogous theorem for edge-disjoint packings: For sufficiently large n, it is possible to pack edge-disjoint copies of G in Q_n so that any proportion r < 1 of the edges of Q_n are covered by the packing.
Źródło:: Discussiones Mathematicae Graph Theory; 2014, 34, 1; 85-93
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Capture-Time Extremal Cop-Win Graphs
Autorzy:: Offner, David
Ojakian, Kerry
Powiązania:: https://bibliotekanauki.pl/articles/32224106.pdf
Data publikacji:: 2021-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: pursuit-evasion games
cops and robbers
cop-win graphs
capture time
extremal graphs
Opis:: We investigate extremal graphs related to the game of Cops and Robbers. We focus on graphs where a single cop can catch the robber; such graphs are called cop-win. The capture time of a cop-win graph is the minimum number of moves the cop needs to capture the robber. We consider graphs that are extremal with respect to capture time, i.e., their capture time is as large as possible given their order. We give a new characterization of the set of extremal graphs. For our alternative approach we assign a rank to each vertex of a graph, and then study which configurations of ranks are possible. We partially determine which configurations are possible, enough to prove some further extremal results. We leave a full classification as an open question.
Źródło:: Discussiones Mathematicae Graph Theory; 2021, 41, 4; 923-948
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja