Xavier Pérez Giménez

(Back to homepage)

Publications

(co-authors who are undergraduate students are marked in red.)
  1. Perfect matchings and Hamiltonian cycles in the preferential attachment model (preprint)
    (with A. Frieze, P. Prałat and B. Reiniger)
    Submitted.

  2. The game of Overprescribed Cops and Robbers played on graphs
    (with A. Bonato, P. Prałat and B. Reiniger)
    Submitted.

  3. Randomly Twisted Hypercubes
    (with A. Dudek, P. Prałat, H. Qi, D. West and X. Zhu)
    Submitted.

  4. Rainbow perfect matchings and Hamilton cycles in the random geometric graph (preprint) (doi)
    (with D. Bal, P. Bennett and P. Prałat)
    Random Structures & Algorithms, accepted.

  5. Subgraphs in non-uniform random hypergraphs
    (with M. Dewar, J. Healy, P. Prałat, J. Proos, B. Reiniger and K. Ternovsky)
    To appear in WAW 2016.

  6. Injective colouring of binomial random graphs
    (with R.M. del Río-Chanona, C. MacRury, J. Nicolaidis, P. Prałat and K. Ternovsky)
    Submitted.

  7. The robot crawler graph process
    (with A. Bonato, R.M. del Río-Chanona, C. MacRury, J. Nicolaidis, P. Prałat and K. Ternovsky)
    Submitted.

    Conference version:
    The robot crawler number of a graph
    In 12th Workshop on Algorithms and Models for the Web-graph (WAW), 2015.

  8. Strong-majority bootstrap percolation on regular graphs with low dissemination threshold (preprint)
    (with D. Mitsche and P. Prałat)
    Stochastic Processes and their Applications, accepted.

  9. A probabilistic version of the game of zombies and survivors on graphs (doi)
    (with A. Bonato, D. Mitsche and P. Prałat)
    Theoretical Computer Science, 655(A):2-14, 2016.

  10. The bondage number of random graphs (preprint)
    (with D. Mitsche and P. Prałat)
    The Electronic Journal of Combinatorics, 23(2), #P2.13, 2016.

  11. On the relation between graph distance and Euclidean distance in random geometric graphs. (preprint) (doi)
    (with J. Díaz, D. Mitsche and G. Perarnau)
    Advances in Applied Probability, 48(3):848-864, 2016.

  12. On-line list colouring of random graphs (preprint) (doi)
    (with A. Frieze, D. Mitsche and P. Prałat)
    The Electronic Journal of Combinatorics, 22(2), #P2.41, 2015.

  13. The domination number of on-line social networks
    (with A. Bonato, M. Lozier, D. Mitsche and P. Prałat)
    In 12th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2015.

  14. Randomized Rumor Spreading: the Effect of the Network Topology (preprint) (doi)
    (with K. Panagiotou, T. Sauerwald and H. Sun)
    Combinatorics, Probability and Computing, 24(2):457–479, 2015.

  15. Arboricity and spanning-tree packing in random graphs (preprint)
    (with P. Gao and C.M. Sato)
    Random Structures & Algorithms, accepted.

    Conference version:
    Arboricity and spanning-tree packing in random graphs with an application to load balancing
    In 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

  16. Asymptotic enumeration of strongly connected digraphs by vertices and edges (preprint) (doi)
    (with N. Wormald)
    Random Structures & Algorithms, 43(1):80-114, 2013.

  17. Disjoint Hamilton cycles in the random geometric graph (preprint) (doi)
    (with T. Müller and N. Wormald)
    Journal of Graph Theory, 68(4):299-322, 2011.

  18. On the chromatic number of random d-regular graphs (preprint) (doi)
    (with G. Kemkes and N. Wormald)
    Advances in Mathematics, 223(1):300-328, 2010.

  19. On the satisfiability threshold of formulas with three literals per clause (doi)
    (with J. Díaz, L. Kirousis and D. Mitsche)
    Theoretical Computer Science, 410(30-32):2920-2934, 2009.

    Conference version:
    A new upper bound for 3-SAT
    In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2008.

  20. Large connectivity for dynamic random geometric graphs
    (with J. Díaz and D. Mitsche)
    IEEE Transactions on Mobile Computing, 8(6):821-835, 2009.

    Conference version:
    On the connectivity of dynamic random geometric graphs
    (with J. Díaz and D. Mitsche)
    In 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.

  21. On the probability of the existence of fixed-size components in random geometric graphs
    (with J. Díaz and D. Mitsche)
    Advances in Applied Probability, 41(2):344-357, 2009.

  22. On the chromatic number of a random 5-regular graph (doi)
    (with J. Díaz, A.C. Kaporis, G.D. Kemkes, L.M. Kirousis and N. Wormald)
    Journal of Graph Theory, 61(3):157-191, 2009.

    Conference (related) version:
    5-regular graphs are 3-colorable with positive probability
    (with J. Díaz, G. Grammatikopoulos, A. Kaporis, L. Kirousis and D. G. Sotiropoulos)
    In 13th Annual European Symposium on Algorithms (ESA), 2005.

    Also:
    Partitioning networks into classes of mutually isolated nodes
    (with J. Díaz, A. Kaporis and L. Kirousis)
    In European Conference on Complex Systems (ECCS), 2005.

  23. Walkers on the cycle and the grid
    (with J. Díaz, M. J. Serna and N. C. Wormald)
    SIAM Journal on Discrete Mathematics, 22(2):747-775, 2008.

    Conference version:
    Connectivity for wireless agents moving on a cycle or grid
    (with J. Díaz, M. J. Serna and N. C. Wormald)
    In 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2005.

  24. Sharp threshold for hamiltonicity of random geometric graphs
    (with J. Díaz and D. Mitsche)
    SIAM Journal on Discrete Mathematics, 21(1):57-65, 2007.

  25. Empirical analysis of the connectivity threshold of mobile agents on the grid.
    In 4th International Workshop on Efficient and Experimental Algorithms (WEA), 2005.



  26. Aspects of Random Graphs: colourings, walkers and Hamiltonian cycles.
    Ph.D. Dissertation, 2007.

(Back to homepage)