Quantum walks are raised for teleporting qubit or qudit. Based on quantum walk teleportation, an arbitrated quantum signature scheme with quantum walks on regular graphs is suggested, in which the entanglement source does not need preparing ahead. In the initial phase, the secret keys are generated via quantum key distribution system. In the signing phase, the signature for the transmitted message is created by the signer. Teleportation of quantum walks on regular graphs is applied to teleporting encrypted message copy from the signer to the verifier. Concretely, the sender encodes the ciphertext of message copy on coin state. Then two-step quantum walks are performed on the initial system state engendering the necessary entangled state for quantum teleportation, which can be the basis of signature generation and verification. In the verifying phase, the verifier verifies the validity of the completed signature under the aid of an arbitrator. Additionally, the applications of random number and public board deter the verifier’s existential forgery and repudiation attacks before the verifier accepts the true message. Analyses show that the suggested arbitrated quantum signature algorithm satisfies the general two requirements, i.e., impossibility of disavowal from the signer and the verifier and impossibility of forgery from anyone. The discussions demonstrate that the scheme may not prevent disavowal attack from the signer and that the corresponding improvements are presented. The scheme may be realizable because quantum walks have experimentally proven to be implementable in different physical systems.