Yes, your wife can open carry without having a CCL or she can CC. You have never needed any type of permit to open carry in Arizona and as of 2010, you don't need a permit to CC either. If you are driving from Arkansas to Vegas, I presume that you will be on I-40. Be aware that I-40 passes through the Navajo Indian Reservation and they have their own laws regarding guns. According to my map, the reservation starts at the NM border and you be on the reservation for about 20 miles. As long as you stay on the interstate you will be fine, the minute that pull over to a road stop (there are a few), you are on the reservation so leave your guns in the car.
If you stop at restaurant that serves alcohol, you can not consume alcohol and must CC with a valid permit (from any state, I believe).
If you are taking I-40, be prepared to see some very pretty and desolate country. I mean you will not see any signs of human habitation other than the interstate and power lines. Also if you are taking I-40, you should make a point to stop at Meteor Crater. It is about 6 miles off I-40 (exit 233) and well worth the trip.
Have a safe trip. I made a similar drive last year when I moved here from Charleston, SC. I drove on I-40 for over 1300 miles.
PS If you get the chance, stop by Hoover Dam as well.