First off, prepositions are tricky words, and it's hard to talk about all the ways they can be used.
That said...
at
We can use at night to mean during the nighttime:
I was there at night.
(notice how I did not say "at the night," which is what you wrote in your question).
in
We can use in the night to mean during the nighttime or at various times during the night:
Hyenas prowl in the night. (at night would work, too)
into
We use into the night to say that something continues for a long time after sunset:
The partygoers reveled late into the night.
on
You are correct, we don't usually say on night or on the night. However, if we expand the phrase, and stipulate which nights we are talking about, then "on (the) nights when..." is a relatively common construct:
The band liked crashing at our place on nights we played at Live Bay.
I try to go to bed early on Sunday nights.
On the nights when we hear the ice cream truck, we'll go outside and buy ice cream.
Now, let's combine some of these together:
We usually lock the front door at night. However, our roommate Micheal is an actor, and he sometimes works late into the night. On the nights Micheal hasn't come home before midnight, we leave the front door unlocked, in case he has forgotten his key.
From the context, it seems likely that omitting "on" was a journalistic decision.
The Associated Press Stye Book, used by journalists and others when writing public press releases, considers "on" before a day/date to be unnecessary, and therefore a waste of space in print. Omitting it is a habit that's a throwback to pre-internet days when paper size mattered :)
A journalist following AP Style might write:
"The event happened here Tuesday, in response to the other event that
occurred June 10."
Both the preposition "on" and the "th" from "10th" are omitted to save space.
In spoken conversation or non-journalistic writing, people typically include "on," even though it's not required for meaning.
Best Answer
Both Riley Francisco and HostileFork have given you different answers. In my opinion, I feel leaves on Monday sounds more correct than leaves Monday. Similarly, arrives on Sunday sounds better than arrives Sunday.
This does not mean that people will still omit the word on.
I believe people will understand the meaning you are trying to say without using the preposition. However, a preposition simply enforces the meaning you are trying to convey.