oalib

Publish in OALib Journal

ISSN: 2333-9721

APC: Only $99

Submit

Search Results: 1 - 10 of 984 matches for " Pawe? Pra?at "
All listed articles are free for downloading (OA Articles)
Page 1 /984
Display every page Item
Sparse graphs are not flammable
PawePra?at
Mathematics , 2012,
Abstract: In this paper, we consider the following \emph{$k$-many firefighter problem} on a finite graph $G=(V,E)$. Suppose that a fire breaks out at a given vertex $v \in V$. In each subsequent time unit, a firefighter protects $k$ vertices which are not yet on fire, and then the fire spreads to all unprotected neighbours of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate $\rho(G)$ of $G$ is defined as the expected percentage of vertices that can be saved when a fire breaks out at a random vertex of $G$. Let $\tau_k = k+2-\frac {1}{k+2}$. We show that for any $\epsilon >0$ and $k \ge 2$, each graph $G$ on $n$ vertices with at most $(\tau_k-\epsilon)n$ edges is not flammable; that is, $\rho(G) > \frac {2\epsilon}{5\tau_k} > 0$. Moreover, a construction of a family of flammable random graphs is proposed to show that the constant $\tau_k$ cannot be improved.
Acquaintance time of random graphs near connectivity threshold
Andrzej Dudek,PawePra?at
Mathematics , 2014,
Abstract: Benjamini, Shinkar, and Tsur stated the following conjecture on the acquaintance time: asymptotically almost surely $AC(G) \le p^{-1} \log^{O(1)} n$ for a random graph $G \in G(n,p)$, provided that $G$ is connected. Recently, Kinnersley, Mitsche, and the second author made a major step towards this conjecture by showing that asymptotically almost surely $AC(G) = O(\log n / p)$, provided that $G$ has a Hamiltonian cycle. In this paper, we finish the task by showing that the conjecture holds in the strongest possible sense, that is, it holds right at the time the random graph process creates a connected graph. Moreover, we generalize and investigate the problem for random hypergraphs.
Bounds and constructions for n-e.c. tournaments
Anthony Bonato,Przemys?aw Gordinowicz,PawePra?at
Contributions to Discrete Mathematics , 2010,
Abstract: Few families of tournaments satisfying the $n$-e.c. adjacency property are known. We supply a new random construction for generating infinite families of vertex-transitive $n$-e.c. tournaments by considering circulant tournaments. Switching is used to generate exponentially many $n$-e.c. tournaments of certain orders. With aid of a computer search, we demonstrate that there is a unique minimum order $3$-e.c. tournament of order $19,$ and there are no $3$-e.c. tournaments of orders $20,$ $21,$ and $22.$
On the Maximum Density of Graphs with Good Edge-Labellings
Abbas Mehrabian,Dieter Mitsche,PawePra?at
Mathematics , 2012,
Abstract: A good edge-labelling of a simple, finite graph is a labelling of its edges with real numbers such that, for every ordered pair of vertices (u,v), there is at most one nondecreasing path from u to v. In this paper we prove that any graph on n vertices that admits a good edge-labelling has at most n log_2(n)/2 edges, and that this bound is tight for infinitely many values of n. Thus we significantly improve on the previously best known bounds. The main tool of the proof is a combinatorial lemma which might be of independent interest. For every n we also construct an n-vertex graph that admits a good edge-labelling and has n log_2(n)/2 - O(n) edges.
The set chromatic number of random graphs
Andrzej Dudek,Dieter Mitsche,PawePra?at
Mathematics , 2015,
Abstract: In this paper we study the set chromatic number of a random graph $G(n,p)$ for a wide range of $p=p(n)$. We show that the set chromatic number, as a function of $p$, forms an intriguing zigzag shape.
Lazy Cops and Robbers played on Graphs
Deepak Bal,Anthony Bonato,William B. Kinnersley,PawePra?at
Mathematics , 2013,
Abstract: We consider a variant of the game of Cops and Robbers, called Lazy Cops and Robbers, where at most one cop can move in any round. We investigate the analogue of the cop number for this game, which we call the lazy cop number. Lazy Cops and Robbers was recently introduced by Offner and Ojakian, who provided asymptotic upper and lower bounds on the lazy cop number of the hypercube. By investigating expansion properties, we provide asymptotically almost sure bounds on the lazy cop number of binomial random graphs $\mathcal{G}(n,p)$ for a wide range of $p=p(n)$. By coupling the probabilistic method with a potential function argument, we also improve on the existing lower bounds for the lazy cop number of hypercubes. Finally, we provide an upper bound for the lazy cop number of graphs with genus $g$ by using the Gilbert-Hutchinson-Tarjan separator theorem.
Rainbow arborescence in random digraphs
Deepak Bal,Patrick Bennett,Colin Cooper,Alan Frieze,PawePra?at
Mathematics , 2014,
Abstract: We consider the Erd\H{o}s-R\'enyi random directed graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let $\mathcal{D}(n,m)$ be a graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ($i=1,2,\ldots, m$) of $\mathcal{D}(n,m)$ independently chooses a colour, taken uniformly at random from a given set of $n(1 + O( \log \log n / \log n)) = n (1+o(1))$ colours. We stop the process prematurely at time $M$ when the following two events hold: $\mathcal{D}(n,M)$ has at most one vertex that has in-degree zero and there are at least $n-1$ distinct colours introduced ($M= n(n-1)$ if at the time when all edges are present there are still less than $n-1$ colours introduced; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether $\mathcal{D}(n,M)$ has a rainbow arborescence (that is, a directed, rooted tree on $n$ vertices in which all edges point away from the root and all the edges are different colours). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is "yes".
To catch a falling robber
William B. Kinnersley,PawePra?at,Douglas B. West
Mathematics , 2014,
Abstract: We consider a Cops-and-Robber game played on the subsets of an $n$-set. The robber starts at the full set; the cops start at the empty set. On each turn, the robber moves down one level by discarding an element, and each cop moves up one level by gaining an element. The question is how many cops are needed to ensure catching the robber when the robber reaches the middle level. Aaron Hill posed the problem and provided a lower bound of $2^{n/2}$ for even $n$ and $\binom{n}{\lceil n/2 \rceil}2^{-\lfloor n/2 \rfloor}$ for odd $n$. We prove an upper bound (for all $n$) that is within a factor of $O(\ln n)$ times this lower bound.
Power of $k$ choices and rainbow spanning trees in random graphs
Deepak Bal,Patrick Bennett,Alan Frieze,PawePra?at
Mathematics , 2014,
Abstract: We consider the Erd\H{o}s-R\'enyi random graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let $\mathcal{G}(n,m)$ be a graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ($i=1,2,..., m$) of $\mathcal{G}(n,m)$ independently chooses precisely $k \in \mathbb{N}$ colours, uniformly at random, from a given set of $n-1$ colours (one may view $e_i$ as a multi-edge). We stop the process prematurely at time $M$ when the following two events hold: $\mathcal{G}(n,M)$ is connected and every colour occurs at least once ($M={n \choose 2}$ if some colour does not occur before all edges are present; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether $\mathcal{G}(n,M)$ has a rainbow spanning tree (that is, multicoloured tree on $n$ vertices). Clearly, both properties are necessary for the desired tree to exist. In 1994, Frieze and McKay investigated the case $k=1$ and the answer to this question is "yes" (asymptotically almost surely). However, since the sharp threshold for connectivity is $\frac {n}{2} \log n$ and the sharp threshold for seeing all the colours is $\frac{n}{k} \log n$, the case $k=2$ is of special importance as in this case the two processes keep up with one another. In this paper, we show that asymptotically almost surely the answer is "yes" also for $k \ge 2$.
The Total Acquisition Number of Random Graphs
Deepak Bal,Patrick Bennett,Andrzej Dudek,PawePra?at
Mathematics , 2014,
Abstract: Let $G$ be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex $u$ can be moved to a neighbouring vertex $v$, provided that the weight on $v$ is at least as large as the weight on $u$. The total acquisition number of $G$, denoted by $a_t(G)$, is the minimum possible size of the set of vertices with positive weight at the end of the process. LeSaulnier, Prince, Wenger, West, and Worah asked for the minimum value of $p=p(n)$ such that $a_t(\mathcal{G}(n,p)) = 1$ with high probability, where $\mathcal{G}(n,p)$ is a binomial random graph. We show that $p = \frac{\log_2 n}{n} \approx 1.4427 \ \frac{\log n}{n}$ is a sharp threshold for this property. We also show that almost all trees $T$ satisfy $a_t(T) = \Theta(n)$, confirming a conjecture of West.
Page 1 /984
Display every page Item


Home
Copyright © 2008-2017 Open Access Library. All rights reserved.