pith. sign in

arxiv: 1907.06378 · v1 · pith:HD66HVXVnew · submitted 2019-07-15 · 🧮 math.CO

Edge-bipancyclicity of bubble-sort star graphs

Jia Guo , Mei Lu This is my paper

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

classification 🧮 math.CO
keywords bubble-sort star graphedge-bipancyclicitybipartite grapheven cyclesinterconnection networkpermutation graphHamiltonian cycle
0
0 comments X

The pith

The bubble-sort star graph BS_n is edge-bipancyclic for n ≥ 3.

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

The paper shows that the n-dimensional bubble-sort star graph BS_n, a bipartite graph with n! vertices, has the property that every edge lies on cycles of all even lengths from 4 to n!. This is established for dimensions n of at least 3. Moreover, there are at least four distinct cycles of each such length through any given edge. Such a result matters for understanding the cycle structure in graphs used as models for interconnection networks in computing.

Core claim

The n-dimensional bubble-sort star graph BS_n is edge-bipancyclic for n≥3 and for each even length l with 4≤l≤n!, every edge of BS_n lies on at least four different cycles of length l.

What carries the argument

Edge-bipancyclicity applied to the bipartite (2n-3)-regular graph BS_n of order n!.

Load-bearing premise

The bubble-sort star graph BS_n is bipartite and (2n-3)-regular of order n! for n≥3.

What would settle it

An explicit check in BS_3 showing that some edge misses a 4-cycle or a 6-cycle would disprove the claim for the smallest case.

Figures

Figures reproduced from arXiv: 1907.06378 by Jia Guo, Mei Lu.

Figure 1
Figure 1. Figure 1: Illustration of BSn for n = 2, 3, 4 Let x = x1x2 · · · xn, y = y1y2 · · · yn ∈ V (BSn), we use ”◦” to denote an operation such that x = y ◦ (i, j) if and only if xi = yj , xj = yi and xk = yk for every k ∈ {1, 2, · · · , n} − {i, j}. Then (x, y) ∈ E(BSn) if and only if y = x ◦ (1, i) or y = x◦ (i−1, i) for some i ∈ {2, 3, · · · , n}. Let x + = x◦ (1, n) and x − = x◦ (n−1, n) 3 [PITH_FULL_IMAGE:figures/ful… view at source ↗
Figure 3
Figure 3. Figure 3: 4-cycles containing (123, 321) in BS3. Now we show that BS4 is edge-bipancyclic. Lemmas 3.1 and 3.2 are the basis of induction for proving BSn to be edge-bipancyclic. Lemma 3.2 BS4 is edge-bipancyclic. Furthermore, every edge of BS4 lies on at least four different cycles of every even length l with 4 ≤ l ≤ 24. Proof. Let (u, v) be an arbitrary edge of BS4. Since BS4 is vertex transitive, we can assume that… view at source ↗
Figure 4
Figure 4. Figure 4: 6-cycles in BS3. cycle C 1 8 1234 1324 3124 3214 2314 2134 2143 1243 1234 C 2 8 1234 1324 3124 3214 2314 4312 4132 2134 1234 C 3 8 1234 1324 3124 3214 3241 2341 2314 2134 1234 C 4 8 1234 1324 3124 4123 4213 3214 2314 2134 1234 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of Claim 1. edge e∗ = (x, y) ∈ E(Hi) − {e 0 i1 , e(i+1)1} that has a coupled pair-edge e 0 = (x 0 , y0 ) ∈ E(BSn(j)) for every i ∈ {1, 2, · · · , k − 1, n} and j ∈ {k, k + 1, · · · , n − 1}. Thus the edge set E(Ck(n−1)!) ∪ {e 0 ,(x, x0 ),(y, y0 )} − {e∗} forms a (k(n − 1)! + 2)-cycle containing e. Since k(n − k) ≥ 4 for n ≥ 5 and 2 ≤ k ≤ n − 1, there are at least four different (k(n − 1)! + 2)… view at source ↗
read the original abstract

The interconnection network considered in this paper is the bubble-sort star graph. The $n$-dimensional bubble-sort star graph $BS_n$ is a bipartite and $(2n-3)$-regular graph of order $n!$. A bipartite graph $G$ is edge-bipancyclic if each edge of $G$ lies on a cycle of all even length $l$ with $4\leq l\leq |V(G)|$. In this paper, we show that the $n$-dimensional bubble-sort star graph $BS_n$ is edge-bipancyclic for $n\ge 3$ and for each even length $l$ with $4\leq l\leq n!$, every edge of $BS_n$ lies on at least four different cycles of length $l$.

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

0 major / 2 minor

Summary. The manuscript proves that the n-dimensional bubble-sort star graph BS_n (bipartite, (2n-3)-regular, order n!) is edge-bipancyclic for all n≥3: for every edge e and every even l with 4≤l≤n!, there exist at least four distinct l-cycles containing e. The argument proceeds by induction on n; base cases n=3 and n=4 are settled by exhaustive enumeration, while the inductive step fixes an arbitrary edge, decomposes BS_n into n copies of BS_{n-1} joined by a perfect matching of a prescribed type, and constructs the required cycles by combining paths inside the subcubes with distinct pairs of crossing edges, handling all parity and size cases for l.

Significance. The result supplies an explicit, multiplicity-four strengthening of the cycle-embedding properties of a standard family of interconnection networks. The inductive construction is fully detailed, the base cases are verified directly, and the argument accounts for the precise lower bound of four cycles without additional assumptions on connectivity or diameter.

minor comments (2)
  1. [§2] §2, definition of the crossing matching: a single sentence clarifying that the matching edges correspond to the star transpositions involving the largest symbol would remove any ambiguity for readers unfamiliar with the recursive construction.
  2. [Theorem 3.1] The statement of the main theorem (Theorem 3.1) repeats the abstract almost verbatim; a compact restatement emphasizing the multiplicity-four claim would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the thorough review and the positive recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity; inductive proof is self-contained

full rationale

The paper presents a direct inductive proof that BS_n is edge-bipancyclic. The definition of BS_n (bipartite, (2n-3)-regular, order n!) is given independently of the claimed cycle property. The argument proceeds by induction on n, with explicit base cases n=3,4 verified by enumeration and an inductive step that constructs cycles by combining paths in subcubes with crossing edges. No fitted parameters, self-definitional equations, load-bearing self-citations, or renamed known results appear. The central existence claim does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definition of the bubble-sort star graph and the usual axioms of graph theory that guarantee the existence of cycles once a construction is given. No numerical parameters are fitted and no new entities are postulated.

axioms (1)
  • domain assumption The bubble-sort star graph BS_n is bipartite and (2n-3)-regular of order n! for n≥3.
    This definition is stated in the abstract and is required for the even-length cycle claim to be meaningful.

pith-pipeline@v0.9.0 · 5650 in / 1209 out tokens · 34218 ms · 2026-05-24T21:36:09.164361+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

22 extracted references · 22 canonical work pages

  1. [1]

    Auletta, A

    A. Auletta, A. Rescigno, V. Scarano, Embedding graphs onto the supercube, IEEE Transactions on Computers 44(4)(1995) 593-597

    work page 1995

  2. [2]

    J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976

    work page 1976

  3. [3]

    H. Cai, H. Liu, M. Lu, Fault-tolerant maximal local-connectivity on Bubble-sort star graphs, Discrete Applied Mathematics 181(2015) 33-40

    work page 2015

  4. [4]

    X. B. Chen, Paired 2-disjoint path covers of multidimensional torus networks with faulty edges, Information Processing Letters 116(2)(2016) 107-110

    work page 2016

  5. [5]

    Z. T. Chou, C. C. Hsu, J. P. Sheu, Bubblesort star graphs: a new interconnection network, International Conference on Parallel and Distributed Systems (1996) 41-48

    work page 1996

  6. [6]

    W. B. Fan, J. X Fan., C. K. Lin, Y. Wang, Y. J. Han, R. C Wang, Opti- mally Embedding 3-Ary n-Cubes into Grids, Journal of Computer Science and Technology 34(2)(2019), 372-387

    work page 2019

  7. [7]

    J. F. Fang, J. Y. Hsiao, C. Y. Tang, Embedding cycles and meshes onto incom- plete hypercubes, International Journal of Computer Mathematics 75(1)(2000) 1-19

    work page 2000

  8. [8]

    M. M. Gu, R. X. Hao, Y. Q. Feng, The pessimistic diagnosability of bubble-sort star graphs and augmented k-ary n-cubes, International Journal of Computer Mathematics: Computer Systems Theory 1(3-4)(2016) 98-112

    work page 2016

  9. [9]

    J. Guo, M. Lu, Conditional diagnosability of bubble-sort star graphs, Discrete Applied Mathematics 201(2016) 141-149

    work page 2016

  10. [10]

    Kikuchi, T

    Y. Kikuchi, T. Araki, Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs, Information Processing Letters 100 (2006) 52-59

    work page 2006

  11. [11]

    C. N. Kuo, I. A. Stewart, Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubes, Theoretical Computer Science 627(2016) 102-106

    work page 2016

  12. [12]

    Latifi, N

    S. Latifi, N. Bagherzadeh, R. R. Gajjala, Fault-tolerant embedding of linear arrays and rings in the star graph, Computers & electrical engineering 23(2) (1997) 95-107. 12

    work page 1997

  13. [13]

    P. Li, M. Xu, Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes, Applied Mathematics and Computation 307(2017) 180-192

    work page 2017

  14. [14]

    J. Li, S. Wang, D. Liu, S. Lin, Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges, Information Sciences, 181(11)(2011) 2260-2267

    work page 2011

  15. [15]

    T. K. Li, C. H. Tsai, J. J. M. Tan, L. H. Hsu, Bipanconnectivity and edge-fault- tolerant bipancyclicity of hypercubes, Information Processing Letters 87(2003) 107-110

    work page 2003

  16. [16]

    Y. C. Lin, On balancing sorting on a linear array, IEEE Transactions on Parallel and Distributed Systems 4(5)(1993) 566-571

    work page 1993

  17. [17]

    M. Liu, H. Liu, Vertex-fault-tolerant cycles embedding on enhanced hypercube networks, Acta Mathematicae Applicatae Sinica, English Series 32(1)(2016) 187- 198

    work page 2016

  18. [18]

    O ´Hallaron, Uniform approach for solving some classical problems on a linear array, IEEE Transactions on Parallel and Distributed Systems 2(2)(1991) 236-241

    D.R. O ´Hallaron, Uniform approach for solving some classical problems on a linear array, IEEE Transactions on Parallel and Distributed Systems 2(2)(1991) 236-241

    work page 1991

  19. [19]

    Sengupta, On ring embedding in hypercubes with faulty nodes and links, Information Processing Letters 68(1998) 207-214

    A. Sengupta, On ring embedding in hypercubes with faulty nodes and links, Information Processing Letters 68(1998) 207-214

    work page 1998

  20. [20]

    I. A. Stewart, Y. Xiang, Bipanconnectivity and bipancyclicity in k-ary n-cubes, IEEE Transactions on Parallel and Distributed Systems 20(1)(2009) 25-33

    work page 2009

  21. [21]

    S. Wang, Z. Wang, M. Wang, The 2-extra connectivity and 2-extra diagnos- ability of bubble-sort star graph networks, The Computer Journal 59(12)(2016) 1839-1856

    work page 2016

  22. [22]

    S. Wang, Z. Wang, M. Wang, The 2-good-neighbor connectivity and 2-good- neighbor diagnosability of bubble-sort star graph networks, Discrete Applied Mathematics 217(2017) 691-706. 13

    work page 2017