Games have not received the full attention of the requirements engineering community. This scenario is becoming more critical as we move towards newer forms of games, such as pervasive games. Pervasiveness (the quality that distinguishes pervasive games from traditional digital games) holds several meanings, including being ubiquitous, permeating something, or spreading something, somewhere, in a physical space. Pervasiveness can be recognized in by the boundaries of the game expanding every time it is played, from the virtual (or fictional) world to the real world. Pervasive games are a new form of digital entertainment that has evolved in different forms, such as alternate reality games, transmedia games, and crossmedia games. Sensor technologies, networking capabilities, augmented reality systems, computer vision technology, the internet, and, especially, mobile devices have been responsible for the rapid evolution of this new form of digital product. This paper is focused on "pervasive mobile games", which we define as context-aware games that use mobile devices. We bear in mind that mobile devices are currently the main driver for fulfilling the promises of pervasive game playing. Our investigations and experiments on this class of games led us to study the quality requirements for pervasive mobile games. Using different information sources, we gathered a set of interrelated characteristics that are crucial to the success of these games. In this paper, we begin to clarify the definition and scope of pervasive mobile games, which are controversial issues in the literature. Using these fundamentals, we propose a two-level conceptual map of non-functional requirements that helps to realize pervasiveness in pervasive mobile games. These non-functional requirements are then associated with a set of questions that help the designers in verifying tasks and operationalizing the requirements of a game. We also propose a dependence matrix for pervasive game qualities that enhances the insight into pervasiveness and reveals important guidelines for the game designers.