Written on the Wall II - Conjecture 316 #
Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc
theorem
WrittenOnTheWallII.GraphConjecture316.conjecture316
{α : Type u_1}
[Fintype α]
[DecidableEq α]
(G : SimpleGraph α)
[DecidableRel G.Adj]
(hG : G.Connected)
(h : Gᶜ.averageDegree ≤ ↑G.pendantVertices.card)
:
WOWII Conjecture 316
Let G be a simple connected graph and let P denote the set of pendant vertices
(vertices of degree 1). If |P| ≥ deg_avg(Gᶜ), then G is well totally dominated,
where deg_avg(Gᶜ) is the average degree of the complement of G.