Search

Let T be a random tree taken uniformly at random from the family of labelled trees on n vertices. In this note, we provide bounds for c ( n ) , the number of sub-trees of T that hold asymptotically almost surely (a.a.s.). With computer support we show that a.a.s. 1 . 4180538 6 n ≤ c ( n ) ≤ 1 . 4195988 1 n . Moreover, there is a strong indication that, in fact, a.a.s. c ( n ) ≤ 1 . 4180618 3 n .

We consider schedules of unit-duration tasks with random dependencies. Formally the schedules are obtained by imposing a random partial order of vertices in an Erdős-Renyi graph. For such schedules, we provide asymptotic formulas for the parallel execution time and for the required number of processors in a greedy allocation scheme as a function of connection probability. We also derive asymptotic bounds for the number of required processors in an optimal allocation scheme. We test our results for small schedule sizes using simulation and conclude that the convergence to asymptotic results is achieved relatively fast in practice. In our simulation experiment, we define and compare the efficiency of Mixed Integer Programming and Constraint Programming approaches to find the exact solution of the optimal allocation scheme and conclude that Constraint Programming is more efficient in our setting. In the last part of the paper, we provide preliminary results of similar analysis for random schedules generated from arbitrary graphs.

Information gathering by crawlers on the web is of practical interest. We consider a simplified model for crawling complex networks such as the web graph, which is a variation of the robot vacuum edge-cleaning process of Messinger and Nowakowski. In our model, a crawler visits nodes via a deterministic walk determined by their weightings which change during the process deterministically. The minimum, maximum, and average time for the robot crawler to visit all the nodes of a graph is considered on various graph classes such as trees, multi-partite graphs, binomial random graphs, and graphs generated by the preferential attachment model.

International audience; Graph burning is a deterministic discrete time graph process that can be interpreted as a model for the spread of influence in social networks. The burning number of a graph is the minimum number of steps in a graph burning process for that graph. In this paper, we consider the burning number of graph products. We find some general bounds on the burning number of the Cartesian product and the strong product of graphs. In particular, we determine the asymptotic value of the burning number of hypercube graphs and we present a conjecture for its exact value. We also find the asymptotic value of the burning number of the strong grids, and using that we obtain a lower bound on the burning number of the strong product of graphs in terms of their diameters. Finally, we consider the burning number of the lexicographic product of graphs and we find a characterization for that.

The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v , and adds the edge u v to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in c ∗ n rounds, where the value of c ∗ is the result of a high dimensional optimization problem. Numerical computations indicate that c ∗ 2 . 61135 . This improves upon the previously best known upper bound of 3 n rounds. We also show that the previously best lower bound of ( ln 2 + ln ( 1 + ln 2 ) + o ( 1 ) ) n is not tight.

A twisted hypercube of dimension k is created from two twisted hypercubes of dimension k − 1 by adding a matching joining their vertex sets, with the twisted hypercube of dimension 0 consisting of one vertex and no edges. We generate random twisted hypercube by generating the matchings randomly at each step. We show that, asymptotically almost surely, joining any two vertices in a random twisted hypercube of dimension k there are k internally disjoint paths of length at most k lg k + O k lg 2 k . Since the graph is k -regular with 2 k vertices, the number of paths is optimal and the length is asymptotically optimal.

Modularity is a graph characteristic which measures the strength of division of a network into clusters (or communities). Networks with high modularity usually have distinguishable clusters with dense connections between the vertices within clusters and sparse connections between vertices of different clusters. In this paper, we investigate the value of modularity in several well-known random graph models.

In this paper, we consider the problem of increasing efficiency of a transportation system through optimizing the behavior of commuters. The assumption is that the time spent in the traffic can be represented by a monetary value and hence introduction of monetary compensations can lead to a more efficient organization of the transportation system. In our model, heterogeneous travelers differently assess the value of their time spent in congestion, hence it is presumably viable to reduce traffic in the most congested streets by introducing a bidding mechanism that will allow the participants who have a lower monetary value of time to receive a compensation financed by the group of commuters that have a higher value of time spend in congestion. We start by presenting a design of a bidding system for optimal allocation of traffic. We analyze the properties of the proposed algorithm and show that it leads to a more efficient allocation of vehicles than the theoretical allocation that could be achieved in the Nash Equilibrium of an uncontrolled transportation network. Subsequently, we verify the proposed auction design via an agent-based simulation model representing the Manhattan area of New York City. The results of our simulation confirm theoretical findings that the introduction of the proposed auction mechanism in a real city settings leads to a more efficient allocation of routes or means of transportation chosen by commuters.

An ordered hypergraph is a hypergraph H with a specified linear ordering of the vertices, and the appearance of an ordered hypergraph G in H must respect the specified order on V ( G ) . In on-line Ramsey theory, Builder iteratively presents edges that Painter must immediately color. The t -color on-line size Ramsey number R t ( G ) of an ordered hypergraph G is the minimum number of edges Builder needs to play (on a large ordered set of vertices) to force Painter using t colors to produce a monochromatic copy of G . The monotone tight path P r ( k ) is the ordered hypergraph with r vertices whose edges are all sets of k consecutive vertices. We obtain good bounds on R t ( P r ( k ) ) . Letting m = r − k + 1 (the number of edges in P r ( k ) ), we prove m t − 1 ∕ ( 3 t ) ≤ R t ( P r ( 2 ) ) ≤ t m t + 1 . For general k , a trivial upper bound is R k , where R is the least number of vertices in a k -uniform (ordered) hypergraph whose t -colorings all contain P r ( k ) (and is a tower of height k − 2 ). We prove R ∕ ( k lg R ) ≤ R t ( P r ( k ) ) ≤ R ( lg R ) 2 + e , where e is a positive constant and t m is sufficiently large in terms of e − 1 . Our upper bounds improve prior results when t grows faster than m ∕ log m . We also generalize our results to l -loose monotone paths, where each successive edge begins l vertices after the previous edge.

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. In each round, each cop moves up one level by gaining an element, and the robber moves down one level by discarding an element. The question is how many cops are needed to ensure catching the robber when the robber reaches the middle level. Alan Hill posed the problem and provided a lower bound of 2 n / 2 for even n and ( n ⌈ n / 2 ⌉ ) 2 − ⌊ n / 2 ⌋ (which is asymptotic to 2 ⌈ n / 2 ⌉ / π n / 2 ) for odd n. Until now, no nontrivial upper bound was known. In this paper, we prove an upper bound that is within a factor of O ( ln ⁡ n ) of this lower bound.

We consider k -cop-win graphs in the binomial random graph G ( n , 1 / 2 ) . It is known that almost all cop-win graphs contain a universal vertex. We generalize this result and prove that for every k ∈ N , almost all k -cop-win graphs contain a dominating set of cardinality k . From this it follows that the asymptotic number of labelled k -cop-win graphs of order n is equal to ( 1 + o ( 1 ) ) ( 1 − 2 − k ) − k n k 2 n 2 / 2 − ( 1 / 2 − log 2 ( 1 − 2 − k ) ) n .

We study the vertex pursuit game of Cops and Robbers, in which cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G . We focus on G d ( n , r ) , a random geometric graph in which n vertices are chosen uniformly at random and independently from [ 0 , 1 ] d , and two vertices are adjacent if the Euclidean distance between them is at most r . The main result is that if r 3 d − 1 > c d log n n then the cop number is 1 with probability that tends to 1 as n tends to infinity. The case d = 2 was proved earlier and independently in Beveridge et al. (2012), using a different approach. Our method provides a tight O ( 1 / r 2 ) upper bound for the number of rounds needed to catch the robber.

In this paper, we consider the firefighter problem on a graph G = ( V , E ) that is either finite or infinite. Suppose that a fire breaks out at a given vertex v ? V . In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible (if G is finite) or to stop the fire from spreading (for an infinite case).The surviving rate ? ( G ) of a finite graph G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a vertex of G that is selected uniformly random. For a finite square grid P n ? P n , we show that 5 / 8 + o ( 1 ) ? ? ( P n ? P n ) ? 67 243 / 105 300 + o ( 1 ) (leaving the gap smaller than 0.0136) and conjecture that the surviving rate is asymptotic to 5/8.We define the surviving rate for infinite graphs and prove it to be 1 / 4 for the infinite square grid, even for more than one (but finitely many) initial fires. For the infinite hexagonal grid we provide a winning strategy if two additional vertices can be protected at any point of the process, and we conjecture that the firefighter has no strategy to stop the fire without additional help. We also show how the speed of the spreading fire can be reduced by a constant multiplicative factor. For triangular grid, we show that two firefighters can slow down the fire in the same sense, which is relevant to the conjecture that two firefighters cannot contain the fire on the triangular grid, and also corrects a previous result of Fogarty (2003).

In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. We consider the process where at each time step, a vertex that has at least as many brushes as incident, contaminated edges, sends brushes down these edges to clean them. Various problems arise, such as determining the minimum number of brushes (called the brush number) that are required to clean the entire graph. Here, we study a new variant of the problem in which no more than k brushes can be sent at any time step.

We consider the number of independent sets in hypergraphs, which allows us to define the independence density of countable hypergraphs. Hypergraph independence densities include a broad family of densities over graphs and relational structures, such as F -free densities of graphs for a given graph F . In the case of k -uniform hypergraphs, we prove that the independence density is always rational. In the case of finite but unbounded hyperedges, we show that the independence density can be any real number in [ 0 , 1 ] . Finally, we extend the notion of independence density via independence polynomials.

In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. Various problems arise, such as determining the minimum number of brushes that are required to clean the entire graph. This number is called the brushing number. Here, we study a new variant of the brushing problem in which one vertex is cleaned at a time, but more than one brush may traverse a dirty edge. In particular, we obtain results on the brushing number of Cartesian products of graphs and trees, as well as upper and lower bounds on the brushing number in the general case.

International audience; We examine a version of the Cops and Robber (CR) game in which the robber is invisible, i.e., the cops do not know his location until they capture him. Apparently this game (CiR) has received little attention in the CR literature. We examine two variants: in the fi rst the robber is adversarial (he actively tries to avoid capture); in the second he is drunk (he performs a random walk). Our goal in this paper is to study the invisible Cost of Drunkenness (iCOD), which is defi ned as the ratio ct_i(G)/dct_i(G), with ct_i(G) and dct_i(G) being the expected capture times in the adversarial and drunk CiR variants, respectively. We show that these capture times are well defi ned, using game theory for the adversarial case and partially observable Markov decision processes (POMDP) for the drunk case. We give exact asymptotic values of iCOD for several special graph families such as d-regular trees, give some bounds for grids, and provide general upper and lower bounds for general classes of graphs. We also give an infi nite family of graphs showing that iCOD can be arbitrarily close to any value in [2,\infty). Finally, we briefly examine one more CiR variant, in which the robber is invisible and "infi nitely fast"; we argue that this variant is signi cantly di fferent from the Graph Search game, despite several similarities between the two games.

We propose a new random graph model–edge popularity–for the web graph and other complex networks, in which edges are deleted over time and an edge is chosen to be deleted with probability inversely proportional to the in-degree of the destination. We show that, with probability tending to one as time tends to infinity, the model generates graphs whose degree distribution follows a power law. Depending on the parameters of the model, the exponent of the power law can be any number in ( 2 , ∞ ) .

We study a generalized version of the protean graph (a probabilistic model of the World Wide Web) with a power law degree distribution, in which the degree of a vertex depends on its age as well as its rank. The main aim of this paper is to study the behaviour of the protean process near the connectivity threshold. Since even above the connectivity threshold it is still possible that the graph becomes disconnected, it is important to investigate the recovery time for connectivity, that is, how long we have to wait to regain the connectivity.

We consider the process of cleaning a network where at each time step, all vertices that have at least as many brushes as incident, contaminated edges, send brushes down these edges and remove them from the network. An added condition is that, because of the contamination model used, the final configuration must be the initial configuration of another cleaning of the network. We find the minimum number of brushes required for trees, cycles, complete bipartite networks; and for all networks when all edges must be cleaned on each step. Finally, we give bounds on the number of brushes required for complete networks.

We consider homomorphism properties of a random graph G(n,p), where p is a function of n. A core H is great if for all [email protected]?E(H), there is some homomorphism from H-e to H that is not onto. Great cores arise in the study of uniquely H-colourable graphs, where two inequivalent definitions arise for general cores H. For a large range of p, we prove that with probability tending to 1 as n->~, [email protected]?G(n,p) is a core that is not great. Further, we give a construction of infinitely many non-great cores where the two definitions of uniquely H-colourable coincide.

International audience; We prove a relationship between the Cleaning problem and the Balanced Vertex-Ordering problem, namely that the minimum total imbalance of a graph equals twice the brush number of a graph. This equality has consequences for both problems. On one hand, it allows us to prove the View the NP-completeness of the Cleaning problem, which was conjectured by Messinger et al. [M.-E. Messinger, R.J. Nowakowski, P. Prałat, Cleaning a network with brushes, Theoret. Comput. Sci. 399 (2008) 191-205]. On the other hand, it also enables us to design a faster algorithm for the Balanced Vertex-Ordering problem [J. Kára, K. Kratochvíl, D. Wood, On the complexity of the balanced vertex ordering problem, Discrete Math. Theor. Comput. Sci. 9 (1) (2007) 193-202].