Verification:
Degree sequence:
(8,8,4,4,4,3,2,2,2,2,2,1)
Havel–Hakimi first produces a zero at step k=2.
Triangle counts:
(1,4,4,1,1,0,1,8,1,3,1,8)
The minimum occurs once, so freq(t_min)=1.
No 3-vertex total dominating set exists: every such set must contain 0, one of {1,2}, and one of {7,11}; choosing 7 leaves vertex 10 undominated, while choosing 11 leaves vertex 8 undominated.
But {0,1,7,9} is a total dominating set, so γₜ(G)=4.
Please verify—and let me know if this counterexample has appeared before!
🚨 Possible counterexample to WOWII / Written on the Wall II Graph Conjecture 291!
I found a connected 12-vertex graph with
γₜ(G) = 4 > k + freq(t_min) = 2 + 1 = 3.
graph6:
KGABFo@?W?~J
So Conjecture 291 appears to be false. 🧵
#GraphTheory#Combinatorics