Written on the Wall II - Conjecture 146

Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc

Definitions

The square of a graph $G$, denoted $G^2$, is the graph on the same vertex set where two distinct vertices are adjacent if and only if their distance in $G$ is at most $2$.

The radius of $G^2$ is the minimum eccentricity of any vertex in $G^2$, i.e., $$\mathrm{rad}(G^2) = \min_{v \in V} \max_{u \in V} \mathrm{dist}_{G^2}(u, v).$$

noncomputable def WrittenOnTheWallII.GraphConjecture146.graphSquareRadius {α : Type u_1} (G : SimpleGraph α) : ℕ

The radius of $G^2$ (the graph square): the minimum eccentricity over all vertices of graphSquare G.

Equations

• WrittenOnTheWallII.GraphConjecture146.graphSquareRadius G = G.graphSquare.radius.toNat

theorem WrittenOnTheWallII.GraphConjecture146.conjecture146 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) (hrad : 0 < graphSquareRadius G) : 2 * G.eccSet G.maxEccentricityVertices ≤ G.largestInducedTreeSize * graphSquareRadius G

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.