Yeah, something happened to brahmins there, they disappeared, but still brahmins on north are alive. Just go there and shovel there. Near main entrance on the right.
Edit: Oh, I misunderstood post, shovel-giver is on south from main brahmin pens. Go on south, until tent and NCR sign, then turn on the left, there will be a pen, but it's empty, there's a NPC who gives you shovel.
