Many of the replies here have surprised, me, especially for a site based around Bushcrafters.
I made my reply based on the fact that if I were alone and travelling the world, I would take a dog that would.
Catch food, both for me and itself
Be an alert guard dog, both against animals and people
Be a Faithful Companion, and not wander off to a more convenient place or food supply
Be obedient, and obey commands instantly
Not require 15llbs of food a day
Be able to withstand the Journey, (some of the breeds proposed could barely stand a walk around the park)
Be small enough to get into a taxi or train
Be small enough for me to control physically should it get out of hand.
Remove any of these factors and your journey could be your last