Sharper Randić index–diameter ratio conjecture for cactus graphs

About 5 years old · traced to

Let GG be a cactus with kk cycles and bb bridges; write nn for its number of vertices, RR for its Randić index, and dd for its diameter. A BC-tree is the block-cut tree of GG, and a graph is longitudinally symmetric when it has the symmetry specified by the paper. Cactus diameter-ratio conjecture. For a nontrivial cactus (b=0b=0),

Rd≥n−(k−1)(3−22)n+k−1,\frac{R}{d}\geq \frac{n-(k-1)(3-2\sqrt 2)}{n+k-1},

with equality if the BC-tree is a path and is longitudinally symmetric. For a cactus with k>0k>0 and b>0b>0,

Rd≥n−(k−1)(3−22)−6+43+423n+k+b−1,\frac{R}{d}\geq \frac{n-(k-1)(3-2\sqrt 2)-6+\frac{4}{\sqrt 3}+4\sqrt{\frac{2}{3}}}{n+k+b-1},

with equality if the BC-tree is a path, the graph has two leaves, and it is longitudinally symmetric. This is proposed as a sharper diameter-ratio bound incorporating cycles and bridges; the supplied text says it is proved only for cacti whose BC-tree is starlike.

References

Primary source

Margaret I. Doig, “Randic index, radius, and diameter for cactus graphs”, arXiv:2107.00071 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.