Rok 2023

• Edge and Pair Queries-Random Graphs and Complexity

  Publikacja

  • D. Dereniowski
  • P. Gordinowicz
  • P. Prałat

  - ELECTRONIC JOURNAL OF COMBINATORICS - Rok 2023

  We investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.

  Pełny tekst do pobrania w portalu

Rok 2022

• Generalized Dold sequences on partially-ordered sets

  Publikacja

  • G. Graff
  • J. Gulgowski
  • M. Lebiedź

  - ELECTRONIC JOURNAL OF COMBINATORICS - Rok 2022

  Dold sequences constitute an important class of integer sequences that play an important role in combinatorics, number theory, topology and dynamical systems. We generalize the notion of Dold sequence for the case of partially ordered sets and describe their properties. In particular we give two alternative descriptions of generalized Dold sequences: by some class of elementary sequences as well as by different...

  Pełny tekst do pobrania w portalu

Rok 2015

• On-line Ramsey Numbers of Paths and Cycles

  Publikacja

  • J. Cyman
  • T. Dzido
  • J. Lapinskas
  • A. Lo

  - ELECTRONIC JOURNAL OF COMBINATORICS - Rok 2015

  Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the \emph{on-line Ramsey number} $\tilde{r}(G,H)$. In...

  Pełny tekst do pobrania w portalu

Rok 2014

• On Symmetry of Uniform and Preferential Attachment Graphs

  Publikacja

  • A. Magner
  • S. Janson
  • G. Kollias
  • W. Szpankowski

  - ELECTRONIC JOURNAL OF COMBINATORICS - Rok 2014

  Motivated by the problem of graph structure compression under realistic source models, we study the symmetry behavior of preferential and uniform attachment graphs. These are two dynamic models of network growth in which new nodes attach to a constant number m of existing ones according to some attachment scheme. We prove symmetry results for m=1 and 2 , and we conjecture that for m≥3 , both models yield asymmetry with high...

  Pełny tekst do pobrania w portalu

Rok 2012

• A construction for the hat problem on a directed graph

  Publikacja

  • R. Hod
  • M. Krzywkowski

  - ELECTRONIC JOURNAL OF COMBINATORICS - Rok 2012

  A team of n players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom he is connected by an arc. The...

  Pełny tekst do pobrania w portalu

• On a Recurrence Arising in Graph Compression

  Publikacja

  • Y. Choi
  • C. Knessl
  • W. Szpankowski

  - ELECTRONIC JOURNAL OF COMBINATORICS - Rok 2012

  In a recently proposed graphical compression algorithm by Choi and Szpankowski (2012), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability p) or the right subtree (with probability 1􀀀p). A new node is created as long as...

  Pełny tekst do pobrania w portalu