pith. sign in

arxiv: 2004.05435 · v5 · submitted 2020-04-11 · 🧮 math.CO

Diameter of General Kn\"odel Graphs

Seyed Reza Musawi , Esameil Nazari Kiashi This is my paper

Pith reviewed 2026-05-24 15:41 UTC · model grok-4.3

classification 🧮 math.CO
keywords Knodel graphsdiameterbipartite graphsregular graphsdistance formulasmodular edgesgraph theory
0
0 comments X

The pith

The diameter of Knödel graphs W_Δ,n equals 1 plus ceil of (n-2) over (2^Δ-2) when n meets a lower bound depending on Δ.

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

The paper first derives explicit formulas for the distance between any two vertices in the Knödel graph W_Δ,n. It then applies those formulas to prove an exact expression for the graph diameter. The result applies to even n at least (2Δ-5)(2^Δ-2)+4. A reader cares because the diameter gives the longest shortest path and therefore the worst-case steps for communication in any network whose structure matches this graph. The expression shows how diameter scales with the number of vertices and the degree parameter.

Core claim

The authors obtain some formulas for evaluating the distance of vertices of the Knödel graph and by them provide the formula diam(W_Δ,n)=1+ceil((n-2)/(2^Δ-2)) for the diameter of W_Δ,n where n≥(2Δ-5)(2^Δ-2)+4.

What carries the argument

The edge rule connecting each vertex (1,j) to the Δ vertices (2,(j+2^k-1) mod (n/2)) for k=0 to Δ-1, which generates the distance relations used to bound the maximum distance.

Load-bearing premise

The distance formulas obtained hold for all vertex pairs when n satisfies the stated lower bound.

What would settle it

Pick Δ=3 and any even n at least (2*3-5)(8-2)+4, build the graph from the vertex pairs and edge rule, run breadth-first search from every vertex to find the true diameter, and check whether it equals 1+ceil((n-2)/6).

read the original abstract

The Kn\"odel graph $W_{\Delta,n}$ is a $\Delta$-regular bipartition graph on $n\ge 2^{\Delta}$ vertices and $n$ is an even integer. The vertices of $W_{\Delta,n}$ are the pairs $(i,j)$ with $i=1,2$ and $0\le j\le n/2-1$. For every $j$, $0\le j\le n/2-1$, there is an edge between vertex $(1, j)$ and every vertex $(2,(j+2^k-1) \mod (n/2))$, for $k=0,1,\cdots,\Delta-1$. In this paper we obtain some formulas for evaluating the distance of vertices of the Kn\"odel graph and by them, we provide the formula $diam(W_{\Delta,n})=1+\lceil\frac{n-2}{2^{\Delta}-2}\rceil$ for the diameter of $W_{\Delta,n}$, where $n\ge (2\Delta-5)(2^{\Delta}-2)+4$.

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 / 3 minor

Summary. The manuscript derives explicit distance formulas between arbitrary vertex pairs in the Knödel graph W_Δ,n (a Δ-regular bipartite graph on n even vertices with n ≥ 2^Δ) by fixing one endpoint at (1,0) and partitioning the second coordinate into residue classes modulo successive powers of 2. These formulas are then maximized to obtain the diameter formula diam(W_Δ,n) = 1 + ⌈(n-2)/(2^Δ-2)⌉ whenever n satisfies the lower bound n ≥ (2Δ-5)(2^Δ-2) + 4.

Significance. If the distance formulas hold, the result supplies a closed-form expression for the diameter of this family of graphs, which are studied in interconnection networks. The proof credits the exhaustive modular case analysis in Sections 3–4, which reduces each distance by exactly one step per generator 2^k and invokes the lower bound on n only to ensure distinct residues and absence of wrap-around collisions; this is a standard, non-circular technique that appears to be carried out without additional global symmetry assumptions.

minor comments (3)
  1. [Abstract] Abstract: the statement of the main theorem could briefly indicate that the proof proceeds via exhaustive residue-class case analysis on the second coordinate, to give readers an immediate sense of the method.
  2. [§4] The lower-bound condition on n is used to guarantee that chosen residues remain distinct inside the first diam steps; a short remark in §4 or the conclusion on whether the bound is tight (or can be relaxed) would strengthen the presentation.
  3. Notation: the vertex set is described as pairs (i,j) with i=1,2 and 0 ≤ j ≤ n/2−1; confirming whether this bipartition labeling is standard in the Knödel-graph literature or adding a one-sentence comparison would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and the recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives explicit distance formulas between arbitrary vertex pairs in W_Δ,n via exhaustive case analysis on the second coordinate modulo successive powers of 2 (Sections 3–4), fixing one endpoint at (1,0) by symmetry. Each case reduces distance by one step using a distinct generator 2^k, and the n lower bound is invoked only to ensure residue distinctness and absence of wrap-around within the first diam steps. The diameter formula is then obtained by maximizing these distances; no fitted parameters, self-citations, or ansatzes are load-bearing, and the result is not equivalent to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definition of the Knödel graph and on the (unstated) distance formulas derived in the paper; no free parameters, invented entities, or non-standard axioms are visible from the abstract.

axioms (1)
  • domain assumption The graph is defined exactly as the bipartite graph with the modular power-of-two connections stated in the abstract.
    This is the object whose diameter is being computed.

pith-pipeline@v0.9.0 · 5717 in / 1077 out tokens · 64180 ms · 2026-05-24T15:41:05.525116+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 internal anchor

  1. [1]

    J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244, Springer, New Yor k, 2008

    work page 2008

  2. [2]

    Fraigniaud and J.G

    P. Fraigniaud and J.G. Peters, Minimum linear gossip gra phs and maximal linear (∆ , k)-gossip graphs, Networks 38 (2001) 150-162

    work page 2001

  3. [3]

    Fertin and A

    G. Fertin and A. Raspaud, A survey on Kn¨ odel graphs, Discrete Applied Mathematics 137 (2004) 173-195

    work page 2004

  4. [4]

    Fertin, A

    G. Fertin, A. Raspaud, H. Schroder, O. Sykora, and I. Vrto , Diameter of the Kn¨ odel graph, Graph-Theoretic Concepts in Computer Science , Springer, (2000) 149-160

    work page 2000

  5. [5]

    Grigoryan and H

    H. Grigoryan and H. Harutyunyan, The shortest path probl em in the Kn¨ odel graph, J. Discrete Algorithms 31 (2015) 40-47

    work page 2015

  6. [6]

    H. A. Harutyunyan and A. L. Liestman, Upper bounds on the b roadcast function using minimum dominating sets, Discrete Math. 312(20) (2012), 2992-2996

    work page 2012

  7. [7]

    H. A. Harutyunyan and G. B. Oad, Exploring the diameter an d broadcast time of general Kn¨ odel graphs using extensive simulations, C3S2E 2014: 25

    work page 2014

  8. [8]

    Heydemann, N

    M-C. Heydemann, N. Marlin and S. Perennes, Cayley graphs with complete rotations , Technical report, Laboratoire de Recherche en Informatique (Orsay), 1997. TR-1155, submi tted for publication

    work page 1997

  9. [9]

    Kn¨ odel, New gossips and telephones, Discrete Mathematics 13 (1975) 95

    W. Kn¨ odel, New gossips and telephones, Discrete Mathematics 13 (1975) 95

    work page 1975

  10. [10]

    Mojdeh, S.R

    D.A. Mojdeh, S.R. Musawi and E. Nazari, Domination Crit ical Kn¨ odel Graphs,Iran J Sci Technol Trans Sci. 43 (2019), 2423-2428. https://doi.org/10.1007/s40995-019 -00710-8

    work page doi:10.1007/s40995-019 2019

  11. [11]

    Mojdeh, S.R

    D.A. Mojdeh, S.R. Musawi and E. Nazari, Domination in 4- regular Kn¨ odel graphs, Open Math. 16 (2018), 816-825

    work page 2018

  12. [12]

    Total domination in cubic Kn\"odel graphs

    D.A. Mojdeh, S.R. Musawi, E. Nazari and N. Jafari Rad, To tal domination in cubic Kn¨ odel Graphs, submitted for publication. arXiv:1804.02532, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  13. [13]

    G. B. Oad, Diameter and Broadcast Time of the Kn¨ odel graph , Masters thesis, Concordia University, 2014

    work page 2014

  14. [14]

    Xueliang, X

    F. Xueliang, X. Xu, Y. Yuansheng and X. Feng, On The Domin ation Number of Kn¨ odel GraphW (3, n), IJPAM, 50(4) (2009), 553-558

    work page 2009