What kind of Fridge do you have? Have you considered adding a solar setup to your vehicle, or is mobility of the setup important?
If a second deep cycle is parallel, does it need more voltage to charge or just time? -- More time, it would charge concurrently 2 x the time.
Would the batteries need to be identical or mixed? I've got a yellowtop in there now. -- It is generally not recommended to mix batteries, and with a solar setup for example, most folks say they should be installed at the same time. I do run mixed batteries though, both about the same age. I have a traxide dual battery system installed.
The Yellow top in good shape is going to give you depends on which yellow top. I run the D34T, that has the top and side posts. It's a 70Ah battery and the 20 hour discharge rate (which is about right for a fridge) is 50Ah.
A fridge is going to use depending on how much your drawing, 2.5 to XX Amps when running, and might run 21 hours out of 24.
By doubling your battery size, you'll double what it can do. The best thing would be to supplement it with 100-200 watts of solar so during the day when you are using most of the power, it will be generated by the solar. At night your drawing less (when it is cooler) and you could get away with one battery, because you are going to generate more during the day than you use, and the battery gets topped up. You could get away with less solar, but on cloudy days, you are not going to generate as much from the solar.
Just tossing this out as a possible option.
Here's a picture of how I set up my solar set (plus the Ham, aprs, and other stuff run on the setup).