As CMOS feature size vertiginously approaches atomic limits, high leakage and power density and exacer-bating IC production costs are prompting for development of new materials, devices, beyond von-Neumann architectures and computing paradigms. Within this context, graphene has emerged as a promising post-Si front runner, owing to its remarkable properties. In this paper, we propose a generic graphene-based complementary-style Boolean gate structure with memory-lock, that allows logic and non-volatile memory co-location. The gate with memory-lock is composed of 2 cells - a pull-up cell performing the gate Boolean function and a pull-down cell performing the inverted Boolean function. Each cell in turn, has a graphene logic layer that carries out Boolean gates computation, and a graphene memory layer for storing the logic state of the gate. As simulation vehicle we considered an inverter gate with memory-lock. Simulation results indicate a current ratio of write/read to/from memory of 1.64.10²for gate input low, and of 2.55. 10²for gate input high. Furthermore, the inverter with memory-lock exhibits a 128× smaller area footprint when compared to the traditional physically separate logic (e.g., 7nm inverter gate) and memory (e.g., 7nm 6T SRAM cell), establishing the potential of proposed structure with memory-lock for more compact and energy efficient future beyond CMOS nano-electronic implementations, and making it highly promising for high-density computations.