On some conjectures of Griggs and graffiti
Ermelinda DeLaViña, Siemion Fajtlowicz, William Waller · DIMACS series in discrete mathematics and theoretical computer science · 2007
Abstract. We discuss a conjecture of J. R. Griggs relating the maximum number of leaves in a spanning tree of a simple, connected graph to the order and independence number of the graph. We prove a generalization of this conjecture made by the computer program Graffiti, and discuss other similar conjectures, including several generalizations of the theorem that the independence number of a simple, connected graph is not less than its radius. 1.