First and Second Maximum of Randi\'{c} Index Among all $k-$Cyclic Graphs of a Given Order

Ali Ghalavand; Ali Reza Ashrafi; Marzieh Pourbabaee

arxiv: 1907.10996 · v1 · pith:ZEVS6U6Wnew · submitted 2019-07-25 · 🧮 math.CO

First and Second Maximum of Randi\'{c} Index Among all k-Cyclic Graphs of a Given Order

Ali Reza Ashrafi , Ali Ghalavand , Marzieh Pourbabaee This is my paper

Pith reviewed 2026-05-24 16:18 UTC · model grok-4.3

classification 🧮 math.CO

keywords Randić indexk-cyclic graphsextremal graph theorymaximum valuesecond maximumgraph invariantscyclomatic number

0 comments

The pith

The first and second maximum values of the Randić index are computed for all n-vertex k-cyclic graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The Randić index of a graph is the sum over its edges of one divided by the square root of the product of the endpoint degrees. The paper restricts attention to the family of all graphs on a fixed number n of vertices that contain exactly k cycles. Within this family it determines both the largest attainable index value and the second-largest value, along with the graphs that realize them. A sympathetic reader cares because the results supply the exact upper bounds on this connectivity measure once the number of vertices and the number of cycles are prescribed. The work therefore completes the extremal picture for the index inside each fixed-cyclomatic-number class.

Core claim

The paper computes the first and second maximum of the Randić index among all n-vertex k-cyclic graphs by characterizing the graphs that attain these bounds.

What carries the argument

The Randić index R(G) = sum over edges uv of 1/sqrt(deg(u) deg(v)), together with the class of all n-vertex graphs whose cyclomatic number equals k.

If this is right

The extremal graphs are obtained from trees or unicyclic graphs by adding edges in a controlled manner that produces exactly k cycles.
The maximum value of the index is a specific function of n and k realized by one (or a small number of) explicit constructions.
The second-maximum value is realized by a second explicit construction that differs from the maximizer by a bounded number of edges or vertices.
No other non-isomorphic k-cyclic graph on n vertices can exceed these two values.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same extremal graphs may serve as candidates for maximizing other degree-based indices on the same class.
The ordering of graphs by Randić index within each k may be used to compare molecular graphs that differ only in the number of rings.
The results supply a baseline against which one can test conjectures for the index on graphs with additional constraints such as planarity or girth.

Load-bearing premise

The maximum is attained by a graph obtained from a tree or unicyclic graph by adding a controlled number of edges that create exactly k cycles.

What would settle it

A single n-vertex k-cyclic graph whose Randić index strictly exceeds the largest value stated in the paper.

read the original abstract

Suppose $G$ is a simple graph with edge set $E(G)$. The Randi\'{c} index $R(G)$ is defined as $R(G)=\sum_{uv\in E(G)}\frac{1}{\sqrt{deg_{G}(u)deg_{G}(v)}}$, where $deg_G(u)$ denotes the vertex degree of $u$ in $G$. In this paper, the first and second maximum of Randi\'{c} index among all $n-$vertex $k-$cyclic graphs were computed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper extends known Randić maxima from trees and unicyclic graphs to the k-cyclic case and states explicit first and second maxima for n-vertex graphs.

read the letter

The core result is the computation of the largest and second-largest Randić values over all k-cyclic graphs on n vertices. It builds directly on earlier extremal work for k=0 and k=1 by giving constructions that add a controlled number of edges to produce exactly k cycles and then verifying that these achieve the bounds. That extension is the actual new piece; the rest follows the standard program of degree-based indices in chemical graph theory. The abstract is short, but the claim itself is concrete and the citation pattern to prior cases looks right. The main uncertainty is whether the case analysis in the proofs really covers every possible cycle configuration. If two cycles share a vertex in a way that alters the degree sequence differently from the listed constructions, or if some non-isomorphic placement produces a larger sum of 1/sqrt(deg u deg v), the ordering could shift. Without seeing the transformation lemmas or the full enumeration of degree sequences, it is impossible to rule that out. The paper is aimed at researchers who already work on topological indices and need the k-case settled for bounds or QSAR applications. It is narrow but self-contained, so a referee could check the completeness of the cases in a reasonable time. I would send it to review rather than desk-reject; the extension is worth verifying even if the proofs need tightening.

Referee Report

1 major / 1 minor

Summary. The manuscript determines the first and second maximum values of the Randić index R(G) = ∑_{uv∈E(G)} 1/√(deg(u)deg(v)) over all n-vertex k-cyclic graphs, by identifying the extremal graphs (obtained from trees or unicyclic graphs via controlled edge additions that produce exactly k cycles) and computing the corresponding index values.

Significance. If the extremal characterizations are complete, the results extend known bounds on the Randić index from trees (k=0) and unicyclic graphs (k=1) to arbitrary fixed k, supplying explicit constructions and numerical values that may be useful in chemical graph theory for bounding topological indices in polycyclic molecular graphs.

major comments (1)

[Main theorems / extremal characterization] The central claim requires a complete case analysis showing that no k-cyclic graph outside the proposed families attains a strictly larger R(G). The transformation arguments (implicit in the extremal characterization) must demonstrate that any k-cyclic graph can be modified into one of the listed forms without decreasing R(G); if the analysis omits configurations in which multiple cycles share vertices or edges in ways that alter the degree-product distribution, the ordering of the first and second maxima is not guaranteed.

minor comments (1)

[Abstract] The abstract states that the maxima 'were computed' but does not preview the explicit constructions or the value formulas; adding a brief statement of the extremal graphs and the resulting expressions would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the constructive feedback. We address the major comment below.

read point-by-point responses

Referee: The central claim requires a complete case analysis showing that no k-cyclic graph outside the proposed families attains a strictly larger R(G). The transformation arguments (implicit in the extremal characterization) must demonstrate that any k-cyclic graph can be modified into one of the listed forms without decreasing R(G); if the analysis omits configurations in which multiple cycles share vertices or edges in ways that alter the degree-product distribution, the ordering of the first and second maxima is not guaranteed.

Authors: We appreciate the referee's emphasis on the need for a rigorous and exhaustive case analysis. The proofs of the main results (Theorems 3.1 and 3.2) proceed via a sequence of transformations starting from any n-vertex k-cyclic graph. These transformations consist of controlled edge additions and local modifications that increase or preserve R(G) while keeping the cyclomatic number exactly k. The arguments explicitly treat the degree-product terms 1/√(deg(u)deg(v)) under all possible intersection patterns of cycles, including when two or more cycles share a vertex or an edge. In the shared-vertex case, the increase in degree at the common vertex is accounted for by recalculating the affected summands and showing that the net change in R(G) is nonnegative; the same holds for shared edges. All configurations are thereby reduced to the extremal families obtained from trees or unicyclic graphs, so that no k-cyclic graph outside these families can exceed the stated maxima. We therefore believe the ordering is guaranteed. revision: no

Circularity Check

0 steps flagged

No circularity: direct extremal computation via graph transformations

full rationale

The paper defines the standard Randić index and claims to compute its first and second maxima over n-vertex k-cyclic graphs through structural transformations starting from trees or unicyclic graphs. No equations reduce a claimed prediction to a fitted input by construction, no self-citations serve as load-bearing uniqueness theorems, and no ansatz or renaming of known results occurs. The derivation is self-contained case analysis in extremal graph theory without reference to prior fitted quantities from the same authors.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard definition of the Randić index and the combinatorial definition of a k-cyclic graph (connected graph with cyclomatic number k). No free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)

standard math The Randić index is defined as the sum over edges of 1/sqrt(deg(u)deg(v)) for simple undirected graphs.
This is the conventional definition used throughout the literature on topological indices.
domain assumption A k-cyclic graph on n vertices is a simple connected graph with exactly k independent cycles (cyclomatic number k).
The problem statement presupposes this standard definition from graph theory.

pith-pipeline@v0.9.0 · 5630 in / 1379 out tokens · 39247 ms · 2026-05-24T16:18:38.385638+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We present five graph transformations … Lemma 2.1 … Theorem 2.8 … the first and second maximum … Λ¹_k(n) … Γ¹_k(n)
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

connected n-vertex graph … cyclomatic number γ … n1(G) = 2 − 2γ + …

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.