**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 (http://www.math.uh.edu/~clarson/wow-july2004.ps)
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 max* _{u∈V(G)} d(u,v)*, and the

**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 *K _{r,r+1}*, which has a Hamiltonian path. It just barely
fails for

**Conjecture 247:** (2007)
If *G* is a connected regular graph, then
*γ _{t}(G) ≥ 2p(G)*, where

**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

**References:**

[D] Ermelinda DeLaViña, Written on the Wall II,
http://cms.dt.uh.edu/faculty/delavinae/research/wowII/index.htm .

[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.