Graph theory and graph polynomials

Results in Graph theory and graph polynomials

• Graphs with five harmonic boundary vertices, subcubic graphs with six, and minimum-boundary two-trees

  Solved with a computer-assisted proof: 227 reduced graphs; subcubic six-boundary graphs and minimum-boundary two-trees also classifiedClassify the connected graphs with exactly five Steinerberger boundary vertices

  Mathematics · Graph theory · standalone Lean package

  A connected graph has exactly five boundary vertices if and only if it is a bridge subdivision of one of 227 reduced graphs; two-connected graphs with at most five boundary vertices have diameter at most two.

  Manuscript: Graphs with five harmonic boundary vertices, subcubic graphs with six, and minimum-boundary two-trees · Lean proof: Graphs with five harmonic boundary vertices, subcubic graphs with six, and minimum-boundary two-trees · Verification: Graphs with five harmonic boundary vertices, subcubic graphs with six, and minimum-boundary two-trees

• Exact three-uniform Berge-path saturation numbers and a counterexample to a conjectured formula

  Disproved for three-uniform hypergraphs; exact formula givenBerge-path saturation conjecture (English–Graber–Kirkpatrick–Methuku–Sullivan, Conjecture 2.4)

  Mathematics · Extremal hypergraph theory · standalone Lean package

  Two loose 8-cycles plus two isolated vertices give a Berge-P₁₀-saturated 3-graph on 34 vertices with 16 edges, not 17; the exact 3-uniform formula holds for all m ≥ 10, n ≥ 2a_m + 1.

  Manuscript: Exact three-uniform Berge-path saturation numbers and a counterexample to a conjectured formula · Lean proof: Exact three-uniform Berge-path saturation numbers and a counterexample to a conjectured formula · Verification: Exact three-uniform Berge-path saturation numbers and a counterexample to a conjectured formula

• Exact Berge saturation numbers of the subdivided star in every uniformity and its minimality among trees

  Exact formula proved in every uniformity; minimality among trees proved for three-uniform hypergraphsBerge saturation numbers of trees and the Berge analogue of the minimum-tree theorem of Faudree, Faudree, Gould and Jacobson

  Mathematics · Extremal hypergraph theory · standalone Lean package

  sat_r(n, Berge-B_a) = ⌊a(n + 1)/((r − 1)a + 1)⌋ for a, r ≥ 3 and n ≥ (r − 1)a + 1; for a ≥ 5, B_a is the unique tree on a + 2 vertices with the least three-uniform saturation coefficient.

  Manuscript: Exact Berge saturation numbers of the subdivided star in every uniformity and its minimality among trees · Lean proof: Exact Berge saturation numbers of the subdivided star in every uniformity and its minimality among trees · Verification: Exact Berge saturation numbers of the subdivided star in every uniformity and its minimality among trees

• Three-uniform Berge-C₄ saturation: linear bounds with coefficients 5/8 and 3/4, the cone spectrum and exact small values

  Linear coefficient bounded between 5/8 and 3/4; exact values for n ≤ 13Three-uniform Berge-C₄ saturation number (English–Graber–Kirkpatrick–Methuku–Sullivan)

  Mathematics · Extremal hypergraph theory · standalone Lean package

  For n ≥ 9, (5n − 3623)/8 ≤ sat₃(n, Berge-C₄) ≤ ⌈(3n − 9)/4⌉; saturated cones are classified and the values for n ≤ 13 are exact.

  Manuscript: Three-uniform Berge-C₄ saturation: linear bounds with coefficients 5/8 and 3/4, the cone spectrum and exact small values · Lean proof: Three-uniform Berge-C₄ saturation: linear bounds with coefficients 5/8 and 3/4, the cone spectrum and exact small values · Verification: Three-uniform Berge-C₄ saturation: linear bounds with coefficients 5/8 and 3/4, the cone spectrum and exact small values

• Ultra-log-concavity of domination sequences of powers of paths and cycles

  ProvedGalvin–Zhang conjecture on ultra-log-concave domination sequences of path and cycle powers

  Mathematics · Graph theory · standalone Lean package

  For every n ≥ 0 and power ℓ ≥ 1, the number d_k of size-k dominating sets of P_n^ℓ and of C_n^ℓ satisfies (k+1)(n−k+1)d_{k−1}d_{k+1} ≤ k(n−k)d_k², so d_k/binom(n,k) is log-concave.

  Manuscript: Ultra-log-concavity of domination sequences of powers of paths and cycles · Lean proof: Ultra-log-concavity of domination sequences of powers of paths and cycles · Verification: Ultra-log-concavity of domination sequences of powers of paths and cycles

• The upper saturation spectrum of Berge triangles in triple systems

  Partially resolvedSaturation spectrum of the Berge triangle in triple systems (Bushaw–English–Heath–Johnston–Rombach)

  Mathematics · Graph theory · standalone Lean package

  For n ≥ 8 every saturated Berge-triangle-free triple system with more than ⌊(n−1)²/8⌋ edges is a paired product F(n,p), so the spectrum above this sharp threshold is exactly {p(n−2p)}.

  Manuscript: The upper saturation spectrum of Berge triangles in triple systems · Lean proof: The upper saturation spectrum of Berge triangles in triple systems · Verification: The upper saturation spectrum of Berge triangles in triple systems

• Leaf deletion can move the unique mode of a tree domination polynomial by two

  CounterexampleBurcroff–O'Brien leaf-deletion mode question for tree domination polynomials

  Mathematics · Graph polynomials · standalone Lean package

  A tree on 7284 vertices has a unimodal domination polynomial with unique mode 3978, while deleting one specified leaf gives a 7283-vertex tree whose domination polynomial is unimodal with unique mode 3976.

  Manuscript: Leaf deletion can move the unique mode of a tree domination polynomial by two · Lean proof: Leaf deletion can move the unique mode of a tree domination polynomial by two · Verification: Leaf deletion can move the unique mode of a tree domination polynomial by two

• Sharp escape of complex domination roots in square flowers

  New theoremLargest complex domination roots of square flowers (n four-cycles sharing one vertex)

  Mathematics · Graph polynomials · standalone Lean package

  For the square flower F_{4,n} of n four-cycles sharing one vertex, the largest domination-root modulus R_n satisfies R_n < 2 + √(4n/W(4n)) for all n ≥ 1 and 4n/R_n² = log(4n) − log log(4n) + o(1).

  Manuscript: Sharp escape of complex domination roots in square flowers · Lean proof: Sharp escape of complex domination roots in square flowers · Verification: Sharp escape of complex domination roots in square flowers

• An entropy increase for a structurally disassortative DomiRank graph

  DisprovedZhang–Zhao DomiRank entropy monotonicity conjecture for disassortative graphs

  Mathematics · Graph theory and matrix analysis · shared Lean library

  A connected graph with 14 vertices and 32 edges has negative degree–log-degree edge covariance and positive DomiRank scores on [251/1000, 63/250], yet its entropy increases by more than 1/10000 nats across that interval.

  Manuscript: An entropy increase for a structurally disassortative DomiRank graph · Lean proof: An entropy increase for a structurally disassortative DomiRank graph · Verification: An entropy increase for a structurally disassortative DomiRank graph