Edge and Pair Queries-Random Graphs and Complexity

  • Dariusz Dereniowski
  • Przemysław Gordinowicz
  • Paweł Prałat
DOI: https://doi.org/10.37236/11159

Abstract

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.

Published
2023-06-02
How to Cite
Dereniowski, D., Gordinowicz, P., & Prałat, P. (2023). Edge and Pair Queries-Random Graphs and Complexity. The Electronic Journal of Combinatorics, 30(2), P2.34. https://doi.org/10.37236/11159
Issue
Volume 30, Issue 2 (2023)
Article Number
P2.34