Nonlinear Dynamics and Chaos by Steven Strogatz is pretty good. Nonlinear dynamics is one of the backbones of complex systems, so it's worth delving into. Graph theory/topology is a close second. Complex Networks by Latora, Nicosia, and Russo is a nice introduction to the graph-theoretical perspective. Complexity: A Guided Tour by Melanie Mitchell is a nice and brief introduction. I can also recommend Spin Glasses and Complexity by Stein and Newman. Spin glasses are basically the "model organism" of complexity science, so it wouldn't hurt to get acquainted with them.