In this work, we investigated how the use of complex networks as catalytic surfaces can affect the phase diagram of the Yaldram–Khan model, as well as how the order of the phase transitions present in the seminal work behaves when randomness is added to the model. The study was conducted by taking into consideration two well-known random networks, the Erdős-Rényi network (ERN), with its long-range randomness, and the random geometric graph (RGG), with its spatially constrained randomness. We perform extensive steady-state Monte Carlo simulations for $$$ {r}_{\mathrm{NO}}=1 $$$, the NO dissociation rate, and show the behavior of the reactive window as a function of the average degree of the networks. Our results also show that, different from the ERN, which preserves the nature of the phase transitions of the original model for all considered average degrees, the RGG seems to have two second-order phase transitions for small values of average degree.