In IoT and embedded systems, small devices require lightweight block ciphers to provide security without being too costly in terms of computation. In this paper, a graph-theoretic lightweight block cipher scheme combining graph based substitution mapping, graph evolution based on dynamic key and traversal based permutation operations is proposed to secure block cipher system. The proposed cipher is based on light weight substitution–permutation network which provides the efficient nonlinear transformation and better diffusion–confusion characteristics. The random graph topology generation makes resistance to differential, linear and related-key cryptanalysis attacks stronger. The experimental results performed with the Python implementation and light-weight hardware emulation reveal a significant advantage over the conventional light-weight ciphers, in terms of 24.9% faster encryption speed, 25.5% less memory occupation and 26.6% lower energy consumption. It offers scalable, secure and energy-efficient cryptographic protection for next-generation IoT and embedded security applications.