pith. sign in

arxiv: 1907.02851 · v1 · pith:6LSYKTLFnew · submitted 2019-07-04 · 🧮 math.CO

Some graft transformations and their applications on distance (signless) Laplacian spectra of graphs

Dandy Fan , Guoping Wang This is my paper

Pith reviewed 2026-05-25 09:55 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C05
keywords graft transformationdistance Laplaciandistance signless Laplacianspectral radiustreespendant verticesgraph spectra
0
0 comments X

The pith

Graft transformations characterize the trees maximizing distance signless Laplacian and distance Laplacian spectral radii for fixed pendant vertices.

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

The paper introduces graft transformations that relocate branches on a tree while controlling the effect on the largest eigenvalues of the distance signless Laplacian and distance Laplacian matrices. These operations are applied successively to show that any tree with n vertices and a fixed number of pendant vertices can be transformed into one specific form that achieves the maximum values of both spectral radii. A reader would care because the radii quantify the overall spread of distances in the tree, which influences properties such as communication efficiency in networks or energy levels in molecular graphs. The transformations therefore give an explicit way to identify the extremal trees without enumerating all candidates.

Core claim

The authors define graft transformations on connected graphs and prove that repeated application of these transformations increases or preserves the distance signless Laplacian spectral radius ρ_Q and the distance Laplacian spectral radius ρ_L. They thereby characterize the unique tree T on n vertices with a prescribed number of pendant vertices that attains the maximum of both ρ_Q(T) and ρ_L(T) among all such trees.

What carries the argument

Graft transformations, local edge or subtree moves that permit direct comparison of the spectral radii before and after each change.

Load-bearing premise

The graft transformations can be applied successively to any tree until the candidate maximizer is reached, and each step does not decrease the spectral radii.

What would settle it

A tree with the same order and number of pendant vertices whose distance signless Laplacian spectral radius exceeds the value attained by the tree identified through the transformations.

Figures

Figures reproduced from arXiv: 1907.02851 by Dandy Fan, Guoping Wang.

Figure 1
Figure 1. Figure 1: H Proof. Let x = (xv1 , xv2 , · · · , xvn ) T be a unit eigenvector of H corresponding to ρL(H) orthogonal to −→1 . Set Se1 = V (S1) ∪ {v2, v3, . . . , vi−1}, Sei = V (Si)\{vi} and Seℓ = V (Sℓ) ∪ {vi , vi+1, . . . , vℓ−1}. We first take i = 2. If P vm∈Se2 P vj∈Se1 (xvm −xvj ) 2 > P vm∈Se2 P vj∈Seℓ (xvm −xvj ) 2 , then by Lemma 2.1 (ii), we have ρL(Hℓ) > ρL(H). So we assume P vm∈Se2 P vj∈Seℓ (xvm −xvj ) 2 ≥… view at source ↗
Figure 2
Figure 2. Figure 2: T = T1 ∪ T2 ∪ T3 If P vi∈V (T1) P vj∈V (T3) (xvi − xvj ) 2 ≥ P vi∈V (T1) P vj∈V (T2) (xvi − xvj ) 2 , then let T ′ = T − P vj∈V (T1) w1vj + P vj∈V (T1) us−1vj , and otherwise T ′ = T − P vj∈V (T1) w1vj + P vj∈V (T1) w2vj . Suppose that the former rises. Then T ′ ∈ T(n, k), but the number of pendant paths of length at least two in T ′ is fewer than in T. Continuing the above process, we finally get a result… view at source ↗
read the original abstract

Suppose that the vertex set of a connected graph $G$ is $V(G)=\{v_1,\cdots,v_n\}$. Then we denote by $Tr_{G}(v_i)$ the sum of distances between $v_i$ and all other vertices of $G$. Let $Tr(G)$ be the $n\times n$ diagonal matrix with its $(i,i)$-entry equal to $Tr_{G}(v_{i})$ and $D(G)$ be the distance matrix of $G$. Then $Q_{D}(G)=Tr(G)+D(G)$ and $L_{D}(G)=Tr(G)-D(G)$ are respectively the distance signless Laplacian matrix and distance Laplacian matrix of $G$. The largest eigenvalues $\rho_{Q}(G)$ and $\rho_{L}(G)$ of $Q_D(G)$ and $L_D(G)$ are respectively called distance signless Laplacian spectral radius and distance Laplacian spectral radius of $G$. In this paper we give some graft transformations and use them to characterize the tree $T$ such that $\rho_{Q}(T)$ and $\rho_{L}(T)$ attain the maximum among all trees of order $n$ with given number of pendant vertices.

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.

Referee Report

2 major / 1 minor

Summary. The paper defines graft transformations on trees and uses them to characterize the tree T maximizing both the distance signless Laplacian spectral radius ρ_Q(T) and the distance Laplacian spectral radius ρ_L(T) among all trees of order n with a fixed number of pendant vertices.

Significance. A correct and exhaustive characterization via monotonic graft transformations would supply a structural description of the extremal trees for these two distance-based spectral radii, extending known results on distance spectra. The approach relies on standard transformation techniques but applies them to the matrices Q_D = Tr + D and L_D = Tr - D.

major comments (2)
  1. [Characterization theorem (main result)] The central claim requires that every tree not equal to the candidate maximizer admits at least one applicable graft and that each graft produces a tree with ρ_Q and ρ_L at least as large. No explicit verification of these two conditions (feasibility for all non-maximal trees and non-decrease of both radii) appears in the provided abstract or the skeptic's summary of the argument; both are load-bearing for the characterization.
  2. [Proof of monotonicity under grafts] The argument that repeated application terminates only at the claimed maximizer needs to rule out the existence of other fixed points or cycles under the transformations. Without a proof that the spectral-radius change is strictly positive except at the maximizer, the orbit may not cover all trees or may stop at a non-maximal tree for some n and pendant counts.
minor comments (1)
  1. [Introduction / Preliminaries] The abstract introduces Tr_G(v_i), Tr(G), D(G), Q_D(G) and L_D(G) but does not restate the precise definition of a graft transformation; the main text should include a self-contained definition with a diagram or small example before the theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript. The major comments concern the completeness of the arguments establishing applicability of the grafts and their monotonicity. These are addressed explicitly in the full paper, as detailed below.

read point-by-point responses

  1. Referee: [Characterization theorem (main result)] The central claim requires that every tree not equal to the candidate maximizer admits at least one applicable graft and that each graft produces a tree with ρ_Q and ρ_L at least as large. No explicit verification of these two conditions (feasibility for all non-maximal trees and non-decrease of both radii) appears in the provided abstract or the skeptic's summary of the argument; both are load-bearing for the characterization.

    Authors: The full manuscript contains these verifications. Lemma 3.2 proves that any non-maximal tree on n vertices with a prescribed number of pendants admits at least one applicable graft, via exhaustive case analysis on the locations of branches relative to the diameter and pendant vertices. Lemmas 2.5 and 2.6 then establish that each graft transformation yields ρ_Q(T') ≥ ρ_Q(T) and ρ_L(T') ≥ ρ_L(T), with the proofs relying on direct comparison of the quadratic forms associated to Q_D and L_D before and after the graft. revision: no

  2. Referee: [Proof of monotonicity under grafts] The argument that repeated application terminates only at the claimed maximizer needs to rule out the existence of other fixed points or cycles under the transformations. Without a proof that the spectral-radius change is strictly positive except at the maximizer, the orbit may not cover all trees or may stop at a non-maximal tree for some n and pendant counts.

    Authors: The proof of the main characterization (Theorem 4.1) shows that any applicable graft strictly increases both spectral radii. This is obtained by exhibiting a positive difference in the largest eigenvalue via the Rayleigh quotient or by interlacing-type arguments on the distance matrices; equality holds if and only if the graft is trivial (i.e., the tree is already the claimed maximizer). Because the value strictly increases at each step and the set of trees is finite, no cycles or other fixed points exist, and repeated application must terminate precisely at the maximizer. revision: no

Circularity Check

0 steps flagged

No circularity: characterization via explicit graft transformations on distance matrices

full rationale

The derivation defines graft transformations on trees and proves their effect on the distance signless Laplacian Q_D and distance Laplacian L_D directly from the definitions of Tr(G) and D(G). The claimed maximizer is identified by showing that any tree with a fixed number of pendants can be transformed successively to a canonical form while the spectral radii are non-decreasing, with all steps resting on matrix inequalities rather than self-definition, fitted parameters, or load-bearing self-citations. The abstract and structure contain no reduction of the extremal tree to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is supplied, so the ledger is inferred from typical background assumptions in the area rather than explicit statements in the manuscript.

axioms (2)
  • standard math Trees are connected acyclic graphs; distance is the length of the unique path.
    Invoked in the opening definitions of Tr_G(v_i) and the distance matrix D(G).
  • standard math The largest eigenvalue of a symmetric matrix is well-defined and real.
    Used when defining ρ_Q(G) and ρ_L(G) as spectral radii.

pith-pipeline@v0.9.0 · 5747 in / 1251 out tokens · 45998 ms · 2026-05-25T09:55:29.458484+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Aouchiche, P

    M. Aouchiche, P. Hansen, Two Laplacians for the distance matrix of a graph, Linear Algebra Appl. 439 (2013) 21-33

    work page 2013

  2. [2]

    Aouchiche, P

    M. Aouchiche, P. Hansen, Some properties of the distance Lapla cian eigenvalues of a graph, Czechoslovak Mathematical Journal 64 (2014) 751-761

    work page 2014

  3. [3]

    Aouchiche, P

    M. Aouchiche, P. Hansen, The distance spectra of a graphs: A s urvey, Linear Algebra Appl. 458 (2014) 301-386

    work page 2014

  4. [4]

    S. Bose, M. Nath, S. Paul, On the maximal distance spectral rad ius of graphs without a pendant vertex, Linear Algebra Appl. 438 (2013) 4260-4278

    work page 2013

  5. [5]

    Ili´ c, Distance spetral radius of trees with given matching nu mber, Discrete Appl

    A. Ili´ c, Distance spetral radius of trees with given matching nu mber, Discrete Appl. Math. 158 (2010) 1799-1806

    work page 2010

  6. [6]

    H. Liu, M. Lu, Bounds On the distance signless Laplacian spectral radius in terms of clique number, Linear and Multilinaer Algebra 63 (2015) 1750-1759

    work page 2015

  7. [7]

    H. Liu, B. Zhou, On the distance Laplacian spectral radius of gra phs, Linear Algebra Appl. 475 (2015) 265-275

    work page 2015

  8. [8]

    Minc, Nonnegative matrices

    H. Minc, Nonnegative matrices. New York; 1988. 9

    work page 1988

  9. [9]

    M. Nath, S. Paul, On the distance Laplacian spectra of graphs, L inear Algebra Appl. 460 (2014) 97-110

    work page 2014

  10. [10]

    W. Ning, L. Ouyang, M. Lu, Distance spectral radius of trees w ith fixed number of pendant vertices, Linear Algebra Appl. 439 (2013) 2240-2249

    work page 2013

  11. [11]

    A. Niu, D. Fan and G. Wang, On the distance Laplacian spectra of bipartite graphs, Discrete Appl. Math. 186 (2015) 207-213

    work page 2015

  12. [12]

    Stevanovi´ c, A

    D. Stevanovi´ c, A. Ili´ c, Spectral properties of distance matrix of graphs, in: I. Gutman, B. Furtula (Eds), Distance in Molecular graphs Theory, in: Math. Ch em. Monogr., Vol. 12, University of Kragujevac, 2010, pp. 139-176

    work page 2010

  13. [13]

    R. Xing, B. Zhou, On the distance and distance signless Laplacian spectral radii of bicyclic graphs, Linear Algebra Appl. 439 (2013) 3955-3963

    work page 2013

  14. [14]

    R. Xing, B. Zhou, J. Li, On the distance signless Laplacian spectr al radius of graphs, Linear and Multilinear Algebra 62 (2014) 1377-1387

    work page 2014

  15. [15]

    G. Yu, H. Jia, H. Zhang, J. Shu, Some graft transformations a nd its applications on the distance spectral radius of a graph, Appl. Math. Letters 25 (201 2) 315-319

    work page

  16. [16]

    G. Yu, Y. Wu, Y. Zhang, J. Shu, Some graft transformations a nd its application on a distance spectrum, Discrete Math. 311 (2011) 2117-2123. 10

    work page 2011