pith. sign in

arxiv: 1907.06245 · v1 · pith:TE2EUDCAnew · submitted 2019-07-14 · 🧮 math.CO

A new bound for the crossing number of wrapped butterflies

Vijaya N , Bharati R , Paul Manuel This is my paper

Pith reviewed 2026-05-24 21:37 UTC · model grok-4.3

classification 🧮 math.CO
keywords crossing numberwrapped butterflygraph drawingcombinatorial boundinterconnection networkedge crossings
0
0 comments X

The pith

The crossing number of wrapped butterflies admits a finer bound after correction of an error in a prior combinatorial argument.

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

This paper identifies an error in an earlier published bound for the crossing number of wrapped butterfly graphs and supplies a revised combinatorial argument. The new bound is strictly finer than the one it replaces. A sympathetic reader would care because the crossing number measures the minimum number of edge crossings required in any drawing of a graph, which directly affects layout efficiency in interconnection networks. If the corrected bound holds, prior estimates of drawing complexity for these graphs are superseded by a more accurate value.

Core claim

The paper claims that an error present in the bound derived in reference [13] for the crossing number of wrapped butterflies can be corrected, and that the resulting new bound is finer than the earlier one.

What carries the argument

The revised combinatorial argument that corrects the error and produces the strictly tighter bound on crossings.

If this is right

  • Any drawing of the wrapped butterfly must contain at least as many crossings as the new lower bound.
  • Earlier published estimates of the crossing number are superseded.
  • Layout algorithms for wrapped butterfly networks must accommodate at least this many crossings.
  • The corrected value narrows the gap between known lower and upper bounds for these graphs.

Where Pith is reading between the lines

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

  • Similar corrections may be possible for crossing-number bounds on other families of wrapped interconnection graphs.
  • If an independent upper-bound construction matches the new lower bound, the exact crossing number would be settled.
  • The refined estimate could improve theoretical models of wire-routing cost in parallel-computing architectures.

Load-bearing premise

The identified error in the prior bound can be fixed by a revised combinatorial argument that yields a valid and strictly finer bound without introducing new gaps.

What would settle it

Exhibiting an explicit drawing of a wrapped butterfly graph whose number of crossings falls below the new bound would falsify the claim.

Figures

Figures reproduced from arXiv: 1907.06245 by Bharati R, Paul Manuel, Vijaya N.

Figure 1
Figure 1. Figure 1: Another labeling of W B(3) 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a). The graph B in W B(4) (b). The ring R in RB(4) Lemma 3.4. [13] The graphs Bk, 1 ≤ k ≤ 2 r−2 , are isomorphic. Lemma 3.5. [13] The graphs Bk, 1 ≤ k ≤ 2 r−2 , are planar. The plane graph associated with B1 is called a ring and is denoted by R; see [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: One fourth diagram of RB(4) 4 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of the three bounds References [1] Barth, D., and Raspaud, A., Two Edge Disjoint Hamilton Cycles in Butterfly Graphs, Info. Proc. Letters 51, 1994, 175-179. [2] Cimikowski, R., Topological Properties of Some Interconnection Network Graphs, Congr. Numer., 121, 1996, 19-32. [3] Cimikowski,R., Imrich Vrtˇo., Improved Bounds for the Crossing Number of the Mesh of Trees, Journal of Interconnection Ne… view at source ↗
read the original abstract

We fix an error in the bound obtained in [13] for the crossing number of wrapped butterflies. The new bound finer than the one provided earlier.

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

1 major / 1 minor

Summary. The manuscript is a short correction note claiming to identify and repair an error in the crossing-number bound for wrapped butterfly graphs derived in reference [13], thereby obtaining a strictly finer bound.

Significance. A valid correction to an existing bound on the crossing number of a well-studied family of graphs would be a modest but useful contribution to topological graph theory. However, because the manuscript supplies neither the original flawed step nor the revised combinatorial argument, the improvement cannot be evaluated and the result cannot be used by subsequent work.

major comments (1)
  1. The manuscript states only that an error in [13] has been fixed and that the resulting bound is finer; it exhibits neither the erroneous step from [13] nor the new counting argument that replaces it. Without this material the central claim is unverifiable.
minor comments (1)
  1. [Abstract] Abstract, second sentence: the clause 'The new bound finer than the one provided earlier' is grammatically incomplete.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the report. We agree that the current short note does not exhibit the specific error from [13] or the replacement argument, rendering the improvement unverifiable as stated. We will revise the manuscript to include these details.

read point-by-point responses

  1. Referee: The manuscript states only that an error in [13] has been fixed and that the resulting bound is finer; it exhibits neither the erroneous step from [13] nor the new counting argument that replaces it. Without this material the central claim is unverifiable.

    Authors: We acknowledge that the manuscript as submitted is too brief to allow verification. In the revised version we will explicitly quote the flawed step from [13], state the corrected counting argument, and show why the new bound is strictly finer. revision: yes

Circularity Check

0 steps flagged

No significant circularity; correction relies on external reference and independent combinatorial argument

full rationale

The paper is a short correction note whose central claim is the repair of a specific error in the crossing-number bound of reference [13] via a revised combinatorial counting argument that yields a strictly finer bound. No equations, definitions, or load-bearing steps are exhibited that reduce by construction to the paper's own inputs, fitted parameters, or a self-citation chain; the derivation is presented as an external correction whose validity rests on the new counting rather than on any internal renaming, ansatz smuggling, or uniqueness theorem imported from the authors' prior work. The manuscript is therefore self-contained against the external benchmark of [13].

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no equations, no parameters, and no new entities, so the ledger is empty.

pith-pipeline@v0.9.0 · 5529 in / 903 out tokens · 34780 ms · 2026-05-24T21:37:03.980969+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

14 extracted references · 14 canonical work pages

  1. [1]

    Barth, D., and Raspaud, A., Two Edge Disjoint Hamilton Cycles in Butterfly Graphs , Info. Proc. Letters 51, 1994, 175-179

    work page 1994

  2. [2]

    Numer., 121, 1996, 19-32

    Cimikowski, R., Topological Properties of Some Interconnection Network Gr aphs, Congr. Numer., 121, 1996, 19-32

    work page 1996

  3. [3]

    Cimikowski,R., Imrich Vr ˇto., Improved Bounds for the Crossing Number of the Mesh of Trees, Journal of Interconnection Networks, 4, 2003, 17-36

    work page 2003

  4. [4]

    R., Johnson, D

    Garey, M. R., Johnson, D. S., Crossing Number is NP-Complete , SIAM J. Alg. Disc. Math. 4, 1983, 312-316

    work page 1983

  5. [5]

    Keller, J., Regular Layouts of Butterfly Networks , Integration 17, 1994, 253-263

    work page 1994

  6. [6]

    T., Introduction to Parallel Algorithms and Architectures: Ar rays, Trees, Hypercubes, Morgan-Kaufman, San Mateo, CA 1992

    Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Ar rays, Trees, Hypercubes, Morgan-Kaufman, San Mateo, CA 1992

    work page 1992

  7. [7]

    H., Yang Y

    Lin, X. H., Yang Y. S., Zheng, W. P., Shi, L., Lu, W. M., The Crossing Numbers of Generalized Petersen Graphs with Small Order , Discrete Appl. Math. 157, 2009, 1016- 1023

    work page 2009

  8. [8]

    Graph Theory 56, 2007, 128-134

    Pan, S., Richter, R.B., The crossing number of K11 is 100 , J. Graph Theory 56, 2007, 128-134

    work page 2007

  9. [9]

    Manuel, Mostafa I., Abd-El-Barr, Indra Rajasingh, Bha rati Rajan, An Efficient Representation of Benes Networks and its Applications , Journal of Discrete Algorithms, 2008, 6, 11-19

    Paul D. Manuel, Mostafa I., Abd-El-Barr, Indra Rajasingh, Bha rati Rajan, An Efficient Representation of Benes Networks and its Applications , Journal of Discrete Algorithms, 2008, 6, 11-19. 6

    work page 2008

  10. [10]

    Manuel, Bharati, R., Indra, R., Vasanthi, B., Improved Bounds on the Crossing Number of Butterfly Network , Discrete Mathematics and Theoretical Computer Science, 15:2, 2013, 87-94

    Paul D. Manuel, Bharati, R., Indra, R., Vasanthi, B., Improved Bounds on the Crossing Number of Butterfly Network , Discrete Mathematics and Theoretical Computer Science, 15:2, 2013, 87-94

    work page 2013

  11. [11]

    B., Thomassen, C., Intersections of Curve Systems and the Crossing Number of C5 × C5, Discrete Comput

    Richter, R. B., Thomassen, C., Intersections of Curve Systems and the Crossing Number of C5 × C5, Discrete Comput. Geom. 13, 1995, 149-159

    work page 1995

  12. [12]

    S´ykora, Imrich Vrˇto., On Crossing Numbers of Hypercubes and Cube Connected Cycles , BIT Numerical Mathematics, 33, 1993, 232-237

    work page 1993

  13. [13]

    Vijaya N, Bharati Rajan, Paul Manuel, Ibrahim Venkat, An Improved Bound for the Crossing Number of Wrapped Butterflies , Proceedings International Workshop on Graph Algorithms, 2015, 33-39

    work page 2015

  14. [14]

    A., Hamilton Cycles and Paths in Butterfly Graphs , Networks, 26, 1995, 145- 150

    Wong, S. A., Hamilton Cycles and Paths in Butterfly Graphs , Networks, 26, 1995, 145- 150. 7

    work page 1995