Cut Decomposition and Induced-Edge Statistics for Degree-Based Edge Indices Under Thorn Reassignments on Regular Cores

Source abstract

Let $G$ be an $r$-regular graph of order n, r ≥ 1, and form $G^{(\mathbf{m})}$ by attaching $m_v$ pendants to each core vertex $v$. For a symmetric degree-based weight $\varphi$, define $$I_\varphi(H) = \sum_{uv \in E(H)} \varphi\bigl(d_H(u), d_H(v)\bigr).$$ Fix the thorn multiset $\{m_v : v \in V(G)\}$, but allow its values to be reassigned among core vertices. A multilevel cut decomposition isolates placement dependence. The cut between the core classes of degrees $a$ and $b$ has coefficient $$-\tfrac12 \, \Delta\varphi(a,b), \quad \text{where } \Delta\varphi(a,b) = \varphi(a,a) - 2\varphi(a,b) + \varphi(b,b).$$ For a fixed core and a finite nonempty set $A$ of attainable degrees, every thorn multiset whose core-vertex degrees lie in $A$ is reassignment-invariant if and only if $G$ is complete or the restricted weight matrix is a symmetric sum matrix. If invariance is required for every connected $r$-regular core, where r ≥ 2, only the sum-matrix case remains. With two thorn levels, $I_\varphi$ is affine in the induced-edge count $e_G(S)$ of the $k$ vertices receiving the larger number. This relation determines the value set and exact range and gives a criterion for fixed-cardinality invariance. When the coefficient is nonzero, the extremal-placement problem is NP-hard on cubic cores. For fixed $k$, the mean and variance of the induced-edge count depend on the core only through its order and regular degree. For $3 \le k \le n-3$, the third factorial moment determines the triangle count, and the index distribution does so as well whenever the affine coefficient is nonzero. For cycles and equal-part complete multipartite cores, the ranges have closed forms. The ordinary, reduced, and Euler Sombor indices are maximized when the heavy-vertex set induces as few core edges as possible, whereas the elliptic Sombor index is maximized when it induces as many as possible. The forgotten index is placement-invariant.