Researchers believe the bone may have been inserted in the animal's mouth by a human after it died, signifying a ritual burial.
The brains of the paleolithic dogs were also removed after their death which could indicate a human's attempt to release the animals' spirits, giving an indication of man's early relationship with dogs.
Dog with a bone: This skull of a dog found with a bone in its mouth may be an early indication of man's relationship with his best friend
Mietje Germonpré a paleontologist at the Royal Belgian Institute of Natural Sciences said the mammoth bone could signify 'that the dog was "fed" to accompany the soul of the dead person on its journey'.
According to the Journal of Archaeological Science, the dog skulls show evidence that humans perforated them in order to remove the brain.
Researchers believe that as better meat was available, it’s unlikely the brains served as food instead it’s possible that the excavation was part of a ritual.
Germonpré told Discovery News that many northern indigenous peoples believed that the head contains the spirit or soul.
She explained: 'Some of these peoples made a hole in the braincase of the killed animal so that the spirit might be released.'
Rob Losey, an associate professor of anthropology at the University of Alberta, told Discovery News that the study shows that the dog domestication occurred much earlier than previously thought.
Man's best friend: The distinctive treatment given to some of the remains indicates that a special connection had developed between people dogs much earlier than previously thought
He said: 'The distinctive treatment given some of the remains also is compelling, and this indicates to me that a special connection had developed between people and some canids quite early on -- long prior to any good evidence for dogs being buried.'
The journal reported that that the skulls discovered clearly showed signs of domestication.as they are significantly shorter than those of fossil or modern wolves, have shorter snouts, and wider braincases and palates than wolves possess.
The dogs were described as large, with an estimated body weight of just over five stone and shoulder height at least 24 inches, resembling a larger and heavier Siberian husky.
The researchers believe the animals were used for hauling meat, bones and tusks from mammoths and firewood.
The dogs are thought to have lived on a diet of mammoth tusks and meat, died when they were between four and eight years old, and suffered from numerous broken teeth during their lifetimes.