Written on the Wall II, conjecture 378 -- definition-109 addendum

1. The subdivided star SS_k really is a tree of the stated shape
  ok   SS_3: n=5, m=4=n-1, connected  => tree
  ok   SS_3: degree sequence [1, 1, 1, 2, 3] = 1^3, 2, 3
  ok   SS_4: n=6, m=5=n-1, connected  => tree
  ok   SS_4: degree sequence [1, 1, 1, 1, 2, 4] = 1^4, 2, 4
  ok   SS_5: n=7, m=6=n-1, connected  => tree
  ok   SS_5: degree sequence [1, 1, 1, 1, 1, 2, 5] = 1^5, 2, 5
  ok   SS_8: n=10, m=9=n-1, connected  => tree
  ok   SS_8: degree sequence [1, 1, 1, 1, 1, 1, 1, 1, 2, 8] = 1^8, 2, 8
  ok   SS_20: n=22, m=21=n-1, connected  => tree
  ok   SS_20: degree sequence [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 20] = 1^20, 2, 20

2. gamma_t(SS_k) = 2 for every k >= 3 (brute force for k <= 9)
  ok   SS_3 (n=5): gamma_t = 2 = 2, witness {c,s}
  ok   SS_4 (n=6): gamma_t = 2 = 2, witness {c,s}
  ok   SS_5 (n=7): gamma_t = 2 = 2, witness {c,s}
  ok   SS_6 (n=8): gamma_t = 2 = 2, witness {c,s}
  ok   SS_7 (n=9): gamma_t = 2 = 2, witness {c,s}
  ok   SS_8 (n=10): gamma_t = 2 = 2, witness {c,s}
  ok   SS_9 (n=11): gamma_t = 2 = 2, witness {c,s}
  ok   SS_10: {c,s} is a total dominating set of size 2
  ok   SS_30: {c,s} is a total dominating set of size 2
  ok   SS_59: {c,s} is a total dominating set of size 2

3. M, D_2 and c(<M>) are as claimed
  ok   SS_3: M = {c} = [0], c(<M>) = 1 = 1
  ok   SS_3: D_2 = {s} = [1]
  ok   SS_4: M = {c} = [0], c(<M>) = 1 = 1
  ok   SS_4: D_2 = {s} = [1]
  ok   SS_7: M = {c} = [0], c(<M>) = 1 = 1
  ok   SS_7: D_2 = {s} = [1]
  ok   SS_15: M = {c} = [0], c(<M>) = 1 = 1
  ok   SS_15: D_2 = {s} = [1]

4. Closed forms for dist_avg(D_2) and for the margin
  ok   n=5: dist_avg = 3/2 = (2n-4)/(n-1) [N], 6/5 = (2n-4)/n [A]
  ok   n=5: margin = -1/2 = (3-n)/(n-1) [N], -1/5 = (4-n)/n [A]
  ok   n=6: dist_avg = 8/5 = (2n-4)/(n-1) [N], 4/3 = (2n-4)/n [A]
  ok   n=6: margin = -3/5 = (3-n)/(n-1) [N], -1/3 = (4-n)/n [A]
  ok   n=7: dist_avg = 5/3 = (2n-4)/(n-1) [N], 10/7 = (2n-4)/n [A]
  ok   n=7: margin = -2/3 = (3-n)/(n-1) [N], -3/7 = (4-n)/n [A]
  ok   n=8: dist_avg = 12/7 = (2n-4)/(n-1) [N], 3/2 = (2n-4)/n [A]
  ok   n=8: margin = -5/7 = (3-n)/(n-1) [N], -1/2 = (4-n)/n [A]
  ok   n=9: closed forms hold
  ok   n=10: closed forms hold
  ok   n=11: closed forms hold
  ok   n=12: dist_avg = 20/11 = (2n-4)/(n-1) [N], 5/3 = (2n-4)/n [A]
  ok   n=12: margin = -9/11 = (3-n)/(n-1) [N], -2/3 = (4-n)/n [A]
  ok   n=13: closed forms hold
  ok   n=14: closed forms hold
  ok   n=15: closed forms hold
  ok   n=16: closed forms hold
  ok   n=17: closed forms hold
  ok   n=18: closed forms hold
  ok   n=19: closed forms hold
  ok   n=20: closed forms hold
  ok   n=21: closed forms hold
  ok   n=22: closed forms hold
  ok   n=23: closed forms hold
  ok   n=24: closed forms hold
  ok   n=25: closed forms hold
  ok   n=26: closed forms hold
  ok   n=27: closed forms hold
  ok   n=28: closed forms hold
  ok   n=29: closed forms hold
  ok   n=30: closed forms hold
  ok   n=31: dist_avg = 29/15 = (2n-4)/(n-1) [N], 58/31 = (2n-4)/n [A]
  ok   n=31: margin = -14/15 = (3-n)/(n-1) [N], -27/31 = (4-n)/n [A]
  ok   n=52: dist_avg = 100/51 = (2n-4)/(n-1) [N], 25/13 = (2n-4)/n [A]
  ok   n=52: margin = -49/51 = (3-n)/(n-1) [N], -12/13 = (4-n)/n [A]
  ok   n=102: dist_avg = 200/101 = (2n-4)/(n-1) [N], 100/51 = (2n-4)/n [A]
  ok   n=102: margin = -99/101 = (3-n)/(n-1) [N], -49/51 = (4-n)/n [A]
  ok   n=502: dist_avg = 1000/501 = (2n-4)/(n-1) [N], 500/251 = (2n-4)/n [A]
  ok   n=502: margin = -499/501 = (3-n)/(n-1) [N], -249/251 = (4-n)/n [A]
  ok   n=1002: dist_avg = 2000/1001 = (2n-4)/(n-1) [N], 1000/501 = (2n-4)/n [A]
  ok   n=1002: margin = -999/1001 = (3-n)/(n-1) [N], -499/501 = (4-n)/n [A]

5. Both margins are negative for all large n and tend to -1
  ok   margin(N) = (3-n)/(n-1) < 0 for every n >= 4
  ok   margin(A) = (4-n)/n < 0 for every n >= 5
  ok   margin(N) -> -1 from above
  ok   margin(A) -> -1 from above

6. The explicit minimum counterexample: SS_3, the 5-vertex fork
  ok   SS_3 has order 5
  ok   gamma_t(SS_3) = 2
  ok   c(<M>) = 1, D_2 = [1]
  ok   RHS under (N) = 5/2 = 5/2
  ok   RHS under (A) = 11/5 = 11/5
  ok   margin (N) = -1/2 = -1/2  => 378 IS FALSE
  ok   margin (A) = -1/5 = -1/5  => 378 IS FALSE

7. No tree of order 4 violates 378 under either normalisation
  ok   P_4: gamma_t=2, margins 0 (N), 1/2 (A) >= 0
  ok   K_{1,3}: gamma_t=2, margins 1 (N), 1 (A) >= 0
  ok   hence the minimum counterexample order under def 109 is exactly 5

====================================================================
83 checks, 0 failures
ALL CHECKS PASSED -- conjecture 378 is false under definition 109,
with an infinite family of counterexamples starting at order 5.