ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let TT be a tree of order n≥3n\geq 3. For a graph GG of order nn, write δk(G)\delta_k(G) for the coefficients of its distance characteristic polynomial and define the normalized coefficients

dk(G)=∣δk(G)∣/2n−k−2,d_k(G)=|\delta_k(G)|/2^{n-k-2},

for 0≤k≤n−20\leq k\leq n-2. A sequence is unimodal if it is nondecreasing up to some index and nonincreasing thereafter. Graham–Lovász's conjecture. The sequence d0(T),…,dn−2(T)d_0(T),\dots,d_{n-2}(T) is unimodal and its peak occurs at ⌊n/2⌋\left\lfloor n/2\right\rfloor.

The conjecture concerns the shape of the coefficients of the distance characteristic polynomial of a tree. Its prescribed peak location was disproved by Collins in 1985, although unimodality is known for stars and paths; hence the conjecture as stated is refuted.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.