Line-graph inequality reversed by attaching long paths to graphs
Reversing the Mostar line-graph inequality with long pendant paths
Discrete Mathematics
Summary
This paper studies a mathematical measure called the Mostar index that compares a graph and its line graph. The authors found that adding long pendant paths to a core graph can reverse the usual inequality between these indices under certain conditions. They precisely describe when and how this reversal happens, depending on the structure and parity of the graph. The findings also solve a previously open problem about graphs with specific cycle counts and degrees.
What this means in practice
- •For network designers: Understand structural graph properties when modifying networks by attaching long chains to optimize connectivity measures related to line graphs.
- •For graph algorithm developers: Develop algorithms that rely on Mostar index behavior by leveraging conditions when inequalities between graphs and their line graphs reverse.
A theory result. No direct application yet.
Authors
Kerem Kat
Abstract
Let $K_t$ be obtained by attaching a pendant path of length $t$ to a fixed rooted graph $K$. We prove that $\mathrm{Mo}(L(K_t))-\mathrm{Mo}(K_t)$, the difference between its line-graph and original Mostar indices, is exactly affine on each parity class beyond a sharp uniform cutoff. The slope depends on distance-level neighbor counts and is positive for every non-bipartite core. Triangle chains give infinitely many graphs with $\mathrm{Mo}(L(G))>\mathrm{Mo}(G)$ at every positive cyclomatic number $c$, with maximum degree three, resolving Alex-Indulal Problem 3.3. At zero slope, a cactus branch-mass formula decides equality; identical vertex profiles need not give identical intercepts. Fixed cores giving equality for all sufficiently long attachments exist exactly when $c$ is odd. Maximum degree three suffices, and at every even $c$ a binary-tree construction gives equality on one eventual parity class.