Open-problem statements, with their sources attached.

WOWII Conjecture 100 (status O):

For a simple connected graph G, α(G) ≤ ⌈(max_v l(v) + 0.5 · diam(Gᶜ)) / 2⌉ where α(G) = G.indepNum is the independence number, max_v l(v) is the maximum over all vertices of the independence number of the neighbourhood (in G), and diam(Gᶜ) is the diameter of the complement Gᶜ. Note:* length(Ḡ) in DeLaVina's original is interpreted here as the diameter of the complement. The hypothesis hGc : Gᶜ.Connected is added so that diam(Gᶜ) is finite (otherwise Gᶜ.ediam = ⊤ and Gᶜ.ediam.toNat collapses silently to 0); see the module docstring above.

WOWII Conjecture 133:

For a simple connected graph $G$, $\operatorname{path}(G) \ge \operatorname{rad}(G) + \lfloor \mathrm{avg}_v\, l(v) \rfloor^{cC_4(G)}$, where $\operatorname{path}(G)$ is the path number of the graph (number of vertices of a largest induced path), $\operatorname{rad}(G)$ is the radius (minimum eccentricity, as a natural number), $\mathrm{avg}_v\, l(v) = l(G)$ is the average independence number of vertex neighbourhoods, and $cC_4(G)$ is the $C_4$-free characteristic function (1 if $G$ is $C_4$-free, not necessarily induced, and 0 otherwise).

We read DeLaVina's bracket notation [average of λ(v)] in the source as the floor (a standard Graffiti.pc convention), hence ⌊l G⌋ in Lean.

WOWII Conjecture 141

For a simple connected graph G, tree(G) ≥ ⌊girth(G) / 2⌋ - 1 + max_v l(v) where tree(G) is the number of vertices of a largest induced tree subgraph, girth(G) is the length of the shortest cycle (0 if acyclic), and l(v) = indepNeighbors G v is the independence number of the neighbourhood of v.

WOWII Conjecture 142:

For a simple connected graph $G$, $\mathrm{tree}(G) \ge (2/3) \cdot \mathrm{girth}(G) + \mathrm{ecc}(B)$ where $\mathrm{tree}(G)$ is the largest induced tree size, $\mathrm{girth}(G)$ is the length of the shortest cycle ($0$ if acyclic), $B$ is the set of boundary vertices (those of maximum eccentricity), and $\mathrm{ecc}(B)$ is the eccentricity of the set $B$.

WOWII Conjecture 144

For a simple connected graph $G$, $\mathrm{tree}(G) \ge \mathrm{girth}(G) - 1 + \mathrm{ecc}(\mathrm{Centers})$ where $\mathrm{tree}(G)$ is the largest induced tree size, $\mathrm{girth}(G)$ is the length of the shortest cycle ($0$ if acyclic), $\mathrm{Centers} = G.\mathrm{center}$ is the set of vertices with minimum eccentricity (the center of $G$), and $\mathrm{ecc}(\mathrm{Centers})$ is the eccentricity of the center set , the maximum distance from any non-center vertex to the nearest center vertex.

WOWII Conjecture 145

For a simple connected graph $G$, $\mathrm{tree}(G) \ge 2 \cdot \mathrm{ecc}(B) / \lambda_{\min}(\overline{G})$ where $\mathrm{tree}(G)$ is the number of vertices in a largest induced subtree, $\mathrm{ecc}(B)$ is the eccentricity of the boundary vertices (eccSet and boundaryVertices), and $\lambda_{\min}(\overline{G})$ is the minimum local independence number of the complement graph.

We state the inequality in the form $\mathrm{tree}(G) \cdot \mathrm{lMin}(\overline{G}) \ge 2 \cdot \mathrm{ecc}(B)$ to avoid division.

WOWII Conjecture 146

For a simple connected graph $G$, $\mathrm{tree}(G) \ge 2 \cdot \mathrm{ecc}(B) / \mathrm{rad}(G^2)$ where $\mathrm{tree}(G)$ is the number of vertices in a largest induced subtree, $\mathrm{ecc}(B)$ is the eccentricity of the boundary vertices of $G$ (eccSet and maxEccentricityVertices), and $\mathrm{rad}(G^2)$ is the radius of the square graph of $G$.

We state the inequality in the form $\mathrm{tree}(G) \cdot \mathrm{rad}(G^2) \ge 2 \cdot \mathrm{ecc}(B)$ to avoid division.

WOWII Conjecture 160

For a simple connected graph $G$, $L_s(G) \ge \max_v l(v) + \max_v T(v) \cdot c_{C_4}(G)$ where:

• $L_s(G) = \mathrm{SimpleGraph.Ls}\, G$ is the maximum number of leaves over all spanning trees of $G$,
• $\max_v l(v)$ is the maximum local independence number over vertices,
• $\max_v T(v)$ is the maximum number of triangles incident to any vertex,
• $c_{C_4}(G)$ is the number of induced 4-cycles in $G$.

WOWII Conjecture 19

If G is connected then the size b(G) of a largest induced bipartite subgraph satisfies b(G) ≥ FLOOR((∑ ecc(v))/(|V|) + sSup (range (l G))), where ecc(v) denotes eccentricity and l(G) is the independence number of neighbourhoods.

WOWII Conjecture 194

For a simple connected graph G, if α(G) ≤ 1 + l_avg(G), then G has a Hamiltonian path. Here α(G) = G.indepNum is the independence number, and l_avg(G) = averageIndepNeighbors G is the average over all vertices of the independence number of the neighbourhood. A Hamiltonian path is a walk visiting every vertex exactly once.

WOWII Conjecture 198a

For a simple connected graph G, if b(G) ≤ 2 + ecc_avg(G), then G has a Hamiltonian path. Here b(G) is the number of vertices in a largest induced bipartite subgraph, and ecc_avg(G) is the average eccentricity of G. A Hamiltonian path is a walk visiting every vertex exactly once.

WOWII Conjecture 2

For a simple connected graph G, Ls(G) ≥ 2 · (l(G) - 1) where l(G) is the average independence number of the neighbourhoods of the vertices of G.

WOWII Conjecture 200

For a simple connected graph G, if tree(G) = ⌈1 + l_avg(G)⌉, then G has a Hamiltonian path. Here tree(G) is the number of vertices of a largest induced tree subgraph, and l_avg(G) = averageIndepNeighbors G is the average over all vertices of the independence number of the neighbourhood. A Hamiltonian path is a walk visiting every vertex exactly once.

WOWII Conjecture 217:

If $G$ is a finite simple connected graph on $n > 1$ vertices and $L_s(G) \le 4 \cdot \chi_{\mathrm{residue}=2}(G) + 2$, then $G$ has a Hamiltonian path. Here $L_s(G)$ is the maximum number of leaves over all spanning trees and $\chi_{\mathrm{residue}=2}(G)$ is the indicator of $\mathrm{residue}(G) = 2$.

WOWII Conjecture 291

For a simple connected graph $G$ with $n > 2$, $\gamma_t(G) \le k + \mathrm{frequency}(t_{\min}(v))$ where:

• $\gamma_t(G)$ is the total domination number,
• $k$ is the first step in which a zero appears in the Havel-Hakimi process,
• $\mathrm{frequency}(t_{\min}(v))$ is the number of vertices achieving the minimum triangle count.

WOWII Conjecture 314:

For every finite simple connected graph $G$ with $n > 1$ vertices, if $G$ is triangle-free and $\mathrm{path}(G) \le 4$, then $G$ is well totally dominated.

Here $\mathrm{path}(G) = \mathrm{largestInducedPathSize}\, G$ is the size of a largest induced path in $G$, defined locally above. Disambiguation.* Earlier revisions of this file used the SimpleGraph.path invariant, but that is the floor of the average distance, not the size of a largest induced path , a different quantity that makes Conjecture 314 vacuous in many cases.

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.

WOWII Conjecture 322

Let G be a simple connected graph on n ≥ 5 vertices. If the maximum over all vertices v of l(v) , the independence number of the neighborhood N(v) of v , is at most 1, then G is well totally dominated.

Here l(v) = α(G[N(v)]) is the independence number of the subgraph induced by the open neighborhood of v.

WOWII Conjecture 40

For a nontrivial connected graph G the size f(G) of a largest induced forest satisfies f(G) ≥ ceil((p(G) + b(G) + 1)/2) where p(G) is the path cover number and b(G) is the largest induced bipartite subgraph size.

WOWII Conjecture 59

For a simple connected graph $G$, the size $f(G)$ of a largest induced forest satisfies $f(G) \ge \lceil \sqrt{\mathrm{residue}(G) \cdot b(G)} \rceil$, where $\mathrm{residue}(G)$ is the Havel-Hakimi residue (the number of zeros remaining after applying the Havel-Hakimi algorithm to the degree sequence until termination) and $b(G)$ is the size of a largest induced bipartite subgraph.

See: Favaron, Mahéo, Saclé (1991) for the residue; DeLaVina's Graffiti.pc for the conjecture.