Some Conjectures of Graffiti.pc (2004-07)

Originators: Graffiti.pc    (presented by D.B. West - REGS 2009)

Background: Graffiti (by S. Fajtlowicz) and Graffiti.pc (by E. DeLaViña) are computer programs that produce conjectures in graph theory. Pointers to information about the programs and to selected lists of conjectures can be found at [D]. A postscript file ( is available containing the first 894 conjectures produced by Fajtlowicz using Graffiti (through 2004). The programs compute combinations of parameters on a database of graphs, mostly conjecturing inequalities. Here we provide a sample of conjectures from Graffiti.pc related to the sizes of various induced subgraphs.

Definitions: For a graph G, let b(G) and t(G) denote the numbers of vertices in the largest induced subgraphs that are bipartite graphs or trees, respectively. Let s(G) denote the number of edges in the largest induced subgraph that is a star; this is also called the local independence number, since it is the largest size of the independence number among the subgraphs induced by vertex neighborhoods.

When G is connected, let L(G) denote the maximum number of leaves among spanning trees of G. Let p(G) denote the minimum number of pairwise disjoint paths that together cover V(G) (this can be viewed as a generalized coloring number). Let δ'(G) denote the next-to-last entry in the degree list of G; it equals δ(G) if G has more than one vertex of smallest degree. The distance d(u,v) between vertices u and v is the minimum length of a u,v-path, the eccentricity of a vertex v is maxu∈V(G) d(u,v), and the radius r(G) is the smallest vertex eccentricity.

Conjecture 84: (2004) If G is connected, then t(G) ≥ 2r(G)/δ(G).

Conjecture 143: (2005) If G is connected and not a tree, then t(G) ≥ (g(G)+1)/δ'(G), where g(G) is the girth of G (smallest cycle length).

Conjecture 161: (2005) If G is connected, then L(G) ≥ s(Ĝ), where Ĝ denotes the complement of G.

Conjectures 174, 177, 179: (2005) For a connected graph G with at least two vertices, the following three quantities are conjectured to be lower bounds on L(G)+b(G): |V(G)|+s(G)-1, 2α(G)+δ'(G), and Δ(G)+s(G)+γ(G), where γ(G) is the minimum size of a dominating set in G

Comments: On August 8, 2005, Graffiti.pc conjectured 13 different lower bounds on L(G)+b(G). These parameters are of interest because L(G) equals |V(G)| minus the minimum size of a connected dominating set (connected dominating sets are the sets of non-leaves in a spanning tree), and b(G) is always at most 2α(G). Conjecture 174 would be a stronger version of Conjecture 7, which involves the independence number. DeLaViña and Waller [DW] proved the weaker versions L(G)+b(G) ≥ |V(G)|+s(G)/2⌉ of Conjecture 174 and L(G)+b(G) ≥ 2α(G)+1 of Conjecture 177.

Conjecture 190a: (2006) If G is a connected graph with at least two vertices and L(G) ≤ δ'(G)+1, then G has a Hamiltonian path.

Conjecture 199: (2006) If G is a connected graph with at least two vertices and κ(G) ≥ t(G)-2, then G has a Hamiltonian path.

Comments: On January 12, 2006, Graffiti.pc conjectured 30 different sufficient conditions for Hamiltonian paths. The hypothesis of Conjecture 199 holds with equality for Kr,r+1, which has a Hamiltonian path. It just barely fails for Kr,r+2, which has no Hamiltonian path. Hence the conjecture is sharp for all values of κ(G).

Conjecture 247: (2007) If G is a connected regular graph, then γt(G) ≥ 2p(G), where γt(G) is the total domination number of G (the minimum size of a set containing a neighbor of every vertex in G).

Comments: On February 23, 2007, Graffiti.pc conjectured 42 different lower bounds for γt(G) (on various classes of graphs). The regularity condition is crucial; the inequality fails spectacularly for stars. It holds with equality for unions of disjoint cliques, where both sides equal twice the number of components. The claim is easy to prove for 1-regular and 2-regular graphs. For 3-regular graphs, a direct proof appears in [DLPWW], but the result also follows from the upper bound by Reed [R] on the path cover number. He showed that p(G) ≤ (n+2)/9 when G is a 3-regular connected graph with n vertices. Trivially, γt(G) ≥ n/r for any r-regular graph.

[D] Ermelinda DeLaViña, Written on the Wall II, .
[DLPWW] DeLaViña, Ermelinda; Liu, Qi; Pepper, Ryan; Waller, Bill; West, Douglas B. Some conjectures of Graffiti.pc on total domination. Proceedings of the Thirty-Eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 185 (2007), 81--95.
[DW] E. DeLaViña and B. Waller, Spanning trees with many leaves and average distance, Electron. J. Combin. 15 (2008), no. 1, Research Paper 33, 16 pp.
[R] Reed, Bruce; Paths, stars and the number three. Combin. Probab. Comput. 5 (1996), no. 3, 277--295.