arxiv: 2604.11267 · v1 · submitted 2026-04-13 · 💻 cs.DM · math.CO

Recognition: unknown

Analyzing Network Robustness via Residual Closeness

Aysun Aytac, Hande Tuncel Golpek, Mehmet Ali Bilici

Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:48 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords middle graphresidual closenessgraph robustnessvertex failurecloseness centralityline graphnetwork vulnerability

0 comments

The pith

The middle graphs of certain special graph classes admit exact closed-form expressions for both closeness and residual closeness after vertex failures.

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

This paper studies network robustness to vertex failures by calculating closeness measures on middle-graph representations of specific graph families. Exact formulas are derived for the closeness values of these middle graphs along with their residual closeness after vertices are removed. The results produce general bounds that apply to wider graph classes and new relations connecting the closeness of a graph to that of its line graph and middle graph. An algorithm is supplied for computing closeness on middle graphs together with performance analysis. These derivations give concrete tools for evaluating how structural changes affect connectivity in networks.

Core claim

Exact expressions are obtained for the closeness of middle graphs belonging to selected special graph classes, together with their residual closeness under vertex failures. These expressions are exploited to establish general bounds for broader graph families and to produce new relations among the closeness values of a graph, its line graph, and its middle graph.

What carries the argument

The middle graph of a graph, formed by replacing each edge with a new vertex and adding appropriate adjacencies, carries the argument by permitting closed-form derivations of closeness and residual closeness.

Load-bearing premise

The selected special graph classes admit exact closed-form closeness expressions without hidden exceptions or constraints that would invalidate the derivations.

What would settle it

Compute the closeness of the middle graph of a small path or cycle using the standard definition and check whether the numerical value matches the closed-form expression given in the paper.

read the original abstract

Networks are inherently vulnerable to vertex failures, making the analysis of their structural robustness a fundamental problem in graph theory. In this study, we investigate the closeness and vertex residual closeness of graphs, with a particular focus on the middle graph representations of certain special graph classes, which provide a richer structural framework for analysis. We derive exact expressions for the closeness values of these middle graphs and determine their residual closeness under vertex failures. By utilizing results obtained from specific graph families, we establish several general bounds for broader graph classes. Furthermore, by exploiting the relationship between the closeness of a graph, its line graphs, and middle graphs, we obtain new results that relate these three structures. In addition, we propose an algorithm for computing closeness in middle graphs and provide a detailed analysis of its performance.

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

Exact formulas for closeness in middle graphs of special families are the solid part, but the claimed general relations and bounds may have gaps in handling distance changes from the middle graph construction.

read the letter

The paper works out exact closeness numbers for the middle graphs of paths, cycles, and a couple other standard families, and then looks at what happens to closeness when you remove a vertex. They also pull out some relations between the closeness of the original graph, its line graph, and the middle graph. They do a decent job laying out the formulas for those specific cases and showing how the middle graph structure lets you compute residual closeness directly. The algorithm they propose for general middle graphs is straightforward and they analyze its time complexity, which is useful if someone wants to implement it. The weaker part is the step from special cases to general bounds. Middle graphs add vertices for edges and connect them to the originals, so distances between original vertices can drop if there's a short path through an edge-vertex. The paper claims new results relating the three structures, but the derivations may miss some of those distance changes or fail to handle cases where removing a vertex splits the graph. The stress-test point about distance adjustments is worth verifying in the proofs. This is targeted at graph theorists who care about network robustness metrics like closeness. A reader already familiar with line graphs and middle graphs will get the most out of the specific calculations. I'd send it for peer review. The exact expressions are checkable and add to the literature on these measures, even if the general claims need more scrutiny in revision.

Referee Report

1 major / 1 minor

Summary. The paper derives exact expressions for the closeness and vertex residual closeness of middle graphs of certain special graph classes, determines their behavior under vertex failures, establishes general bounds for broader classes using results from these families, obtains new relations linking closeness in a graph G, its line graph L(G), and middle graph M(G), and proposes an algorithm for computing closeness in middle graphs along with a performance analysis.

Significance. If the derivations are correct, the work advances the analysis of network robustness by providing closed-form expressions for closeness-based vulnerability measures on middle graphs and by relating these measures across standard graph transformations. The exact results for special classes and the algorithmic contribution are clear strengths; the general bounds, if rigorously established without hidden case distinctions, would extend the utility to wider graph families.

major comments (1)

[Section deriving relations between G, L(G), and M(G)] The section deriving relations between closeness of G, L(G), and M(G) does not explicitly enumerate distance adjustments for original vertices (now connected via edge-vertices and incidence edges in M(G)) or for mixed vertex pairs after a vertex failure removes both a vertex and its incident edges; without such case analysis (e.g., for degree-1 vertices or disconnecting failures), the claimed general bounds for broader classes rest on an unverified assumption that the special-class expressions transfer directly.

minor comments (1)

[Abstract] The abstract states that 'specific graph families' are used to obtain general bounds but does not name the families; adding this detail would improve clarity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thorough review and valuable feedback. We will revise the manuscript to include explicit case analyses for the distance relations in middle graphs as suggested, thereby strengthening the support for our general bounds.

read point-by-point responses

Referee: [Section deriving relations between G, L(G), and M(G)] The section deriving relations between closeness of G, L(G), and M(G) does not explicitly enumerate distance adjustments for original vertices (now connected via edge-vertices and incidence edges in M(G)) or for mixed vertex pairs after a vertex failure removes both a vertex and its incident edges; without such case analysis (e.g., for degree-1 vertices or disconnecting failures), the claimed general bounds for broader classes rest on an unverified assumption that the special-class expressions transfer directly.

Authors: We agree that providing a more detailed case-by-case analysis of distances would improve the clarity of the relations section. Although our derivations are based on the standard definition of the middle graph M(G), which consists of vertices from V(G) and E(G) with appropriate adjacencies, and we have used this to relate closeness measures, we recognize the benefit of explicitly listing adjustments for pairs of original vertices, original and edge-vertices, and the impact of vertex removals (which remove the vertex and its incident edge-vertices). We will add this enumeration in the revised version, including considerations for low-degree vertices and connectivity changes. This will confirm that the bounds derived from special classes apply more generally without unverified assumptions. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations rely on explicit graph definitions and case-by-case exact computations

full rationale

The paper computes exact closeness and residual closeness formulas for middle graphs of specific families (paths, cycles, etc.) directly from the standard definitions of distance sums and middle-graph construction (original vertices plus edge-vertices with incidence edges). These closed-form expressions are then used to obtain bounds for general graphs and relations to line graphs. No step reduces a claimed prediction to a fitted parameter, renames a known result, or rests on a self-citation whose content is itself unverified within the paper. All load-bearing steps are self-contained algebraic derivations from the given graph operations and distance definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard graph theory definitions without introducing free parameters, new entities, or ad-hoc axioms beyond domain assumptions.

axioms (1)

standard math Standard definitions of graph closeness, vertex residual closeness, middle graphs, and line graphs from prior literature.
Invoked throughout for deriving expressions and bounds on middle graphs of special classes.

pith-pipeline@v0.9.0 · 5431 in / 1096 out tokens · 24329 ms · 2026-05-10T15:48:15.238007+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 1 canonical work pages

[1]

Aytac, Z

A. Aytac, Z. Odabas. Residual closeness of wheels and related networks.Int. J. F ound. Comput. Sci., 2011.22:1229

2011
[2]

Aytac, Z

A. Aytac, Z. Odabas. Residual closeness for helm and sunflower graphs.TWMS J. Appl. Eng. Math., 2017. 7:209

2017
[3]

Aytac, Z

A. Aytac, Z. Odabas. Network robustness and residual closeness.RAIRO Oper . Res., 2018.52:839

2018
[4]

Aytac, Z

A. Aytac, Z. Odabas. Robustness of regular caterpillars.Int. J. F ound. Comput. Sci., 2017.28:835. 20H. Tuncel Golpek, M.A. Bilici, A. Aytac/Analyzing Network Robustness

2017
[5]

Aytac, T

A. Aytac, T. Turaci. Closeness centrality in some splitting networks.Comput. Sci. J. Moldova, 2018. 26:251

2018
[6]

C. A. Barefoot, R. Entringer, H. Swart. Vulnerability in graphs: a comparative survey.J. Combin. Math. Combin. Comput., 1987.1:13

1987
[7]

Buckley, F

F. Buckley, F. Harary. Distance in graphs. Addison-Wesley, 1990

1990
[8]

Chartrand, L

G. Chartrand, L. Lesniak, P. Zhang. Graphs and Digraphs. Chapman and Hall/CRC, 2015

2015
[9]

V . Chvatal. Tough graphs and Hamiltonian circuits.Discrete Math., 1973.5:215

1973
[10]

Dangalchev

C. Dangalchev. Residual closeness and generalized closeness.Int. J. F ound. Comput. Sci., 2011.22:1939

2011
[11]

Dangalchev

C. Dangalchev. Closeness of splitting graphs.C. R. Acad. Bulg. Sci., 2020.73:461

2020
[12]

Dangalchev

C. Dangalchev. Residual closeness of generalized thorn graphs.Fundam. Inform., 2018.162:1

2018
[13]

Dangalchev

C. Dangalchev. Closeness of some graph operations. arXiv:2308.14491

work page arXiv
[14]

Dangalchev

C. Dangalchev. Residual closeness in networks.Physica A, 2006.365:556

2006
[15]

L. Freeman. Centrality in social networks: conceptual clarification.Soc. Networks, 1978.1:215

1978
[16]

Hamada, I

T. Hamada, I. Yoshimura. Traversability and connectivity of the middle graph of a graph.Discrete Math., 1976.14:247

1976
[17]

F. Harary. Graph Theory. Addison-Wesley, 1994

1994
[18]

Frank, I

H. Frank, I. T. Frisch. Analysis and design of survivable networks.IEEE Trans. Commun. Technol., 1970. 18:501

1970
[19]

Latora, M

V . Latora, M. Marchiori. Efficient behavior of small-world networks.Phys. Rev. Lett., 2001.87:198701

2001
[20]

Odabas, A

Z. Odabas, A. Aytac. Residual closeness in cycles and related networks.Fundam. Inform., 2013.124:297

2013
[21]

Turaci, M

T. Turaci, M. Okten. Vulnerability of Mycielski graphs via residual closeness.Ars Combin., 2018. 118:419

2018
[22]

Turaci, V

T. Turaci, V . Aytac. Residual closeness of splitting networks.Ars Combin., 2017.130:17

2017