pith. sign in

arxiv: 2508.10834 · v2 · submitted 2025-08-14 · 🧮 math.CO

Quadratic Embedding Constants of Cartesian Products and Joins of Graphs

Projesh Nath Choudhury , Raju Nandi This is my paper

Pith reviewed 2026-05-18 22:50 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C1205C50
keywords quadratic embedding constantgraph joinCartesian productEuclidean embeddingSchoenberg criterionQE classgraph operations
0
0 comments X

The pith

Joins of an arbitrary graph with a regular graph have a closed-form quadratic embedding constant.

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

The paper derives general formulas for the quadratic embedding constant of the join of an arbitrary graph with a regular graph or a complete multipartite graph. It also provides a lower bound for the QEC of Cartesian products of any two connected graphs and exact formulas when one graph is complete or complete bipartite. These formulas matter because they allow direct computation of the constant for many composite graphs from the properties of their factors, linking graph operations to Euclidean distance realizability. Sympathetic readers would see this as extending the reach of distance geometry techniques to new families of graphs without case-by-case analysis.

Core claim

We derive a general formula for the QEC of the join of an arbitrary graph with a regular graph and with a complete multipartite graph. As an application, we explicitly compute the QEC for several classes of graphs and provide new examples of graphs of QE class. We also establish a lower bound for the quadratic embedding constant of the Cartesian product of two arbitrary connected graphs. Furthermore, as an extremal case, we derive concise formulas for the quadratic embedding constants of the Cartesian product of an arbitrary graph G with a complete graph and with a complete bipartite graph, expressed in terms of qec(G).

What carries the argument

The quadratic embedding constant (QEC) defined through the Schoenberg criterion on the distance matrix of the graph, which serves as the measure of Euclidean embeddability for the constructed graphs under join and product operations.

If this is right

  • The QEC can be computed explicitly for joins involving regular graphs without solving optimization problems.
  • Several new classes of graphs are shown to belong to the QE class through these constructions.
  • Lower bounds on QEC for Cartesian products provide necessary conditions for Euclidean embeddability of product graphs.
  • When one factor is a complete graph, the QEC of the product reduces to a simple expression involving only the QEC of the other factor.

Where Pith is reading between the lines

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

  • These formulas may help in studying the embeddability of more complex network structures built iteratively from basic graphs.
  • The lower bound for products could be used to compare embeddability across different graph products in applications like sensor network localization.
  • Further work might explore whether similar closed forms exist for other binary graph operations.

Load-bearing premise

The join formulas require one graph to be regular or complete multipartite, while the overall derivations assume all graphs are finite, simple, and connected.

What would settle it

Calculate the quadratic embedding constant from the definition using the distance matrix for the join of a small path graph and a small cycle graph, then verify if the numerical value agrees with the general formula.

Figures

Figures reproduced from arXiv: 2508.10834 by Projesh Nath Choudhury, Raju Nandi.

Figure 1
Figure 1. Figure 1: P4, C3 and P4 + C3 (Left to right) In 2017, Obata [14] derived an interesting formula for the quadratic embedding constant of a graph join using its adjacency matrix. Proposition 2.5. [14, Proposition 2.1.] Let G1 = (V1, E1) and G2 = (V2, E2) be two disjoint graphs and let V = V1 ∪ V2. Then QEC(G1 + G2) = −2 − min{⟨f, AG1+G2 f⟩ : f ∈ C(V ), ⟨f, f⟩ = 1, ⟨e, f⟩ = 0} [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: P3, C3 and P3 × C3 (Left to right) Let G1 and G2 be two connected graphs with vertex set V1 = {u1, u2, . . . , um} and V2 = {v1, v2, . . . , vn}, respectively. Suppose that Mk = {(uk, v1),(uk, v2), . . . ,(uk, vn)} for all k ∈ [m]. Then the vertex set of G1 × G2 is ∪ m k=1Mk. Then the distance matrix DG1×G2 is an m × m block matrix whose each block is of order n. Let (ui , vp) and (uj , vq) be two arbitrar… view at source ↗
read the original abstract

The quadratic embedding constant (QEC) of a finite, simple, connected graph originated from the classical work of Schoenberg [Ann. of Math., 1935] and [Trans. Amer. Math. Soc., 1938] on Euclidean distance geometry. In this article, we study the QEC of graphs in terms of two graph operations: the Cartesian product and the join of graphs. We derive a general formula for the QEC of the join of an arbitrary graph with a regular graph and with a complete multipartite graph. As an application of these results, we explicitly compute the QEC for several classes of graphs and provide new examples of graphs of QE class. We also establish a lower bound for the quadratic embedding constant of the Cartesian product of two arbitrary connected graphs. Furthermore, as an extremal case, we derive concise formulas for the quadratic embedding constants of the Cartesian product of an arbitrary graph G with a complete graph and with a complete bipartite graph, expressed in terms of $\qec(G)$.

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

Summary. The manuscript studies the quadratic embedding constant (QEC) of finite simple connected graphs under the Cartesian product and join operations. It derives a general closed-form formula for the QEC of the join of an arbitrary graph with a regular graph and with a complete multipartite graph by applying the Schoenberg criterion to the squared-distance matrix of the resulting graph. As applications, explicit QEC values are computed for several graph classes, yielding new examples of graphs belonging to the QE class. The paper also proves a lower bound on the QEC of the Cartesian product of any two connected graphs and gives concise formulas, expressed in terms of QEC(G), for the Cartesian product of G with a complete graph or a complete bipartite graph.

Significance. If the derivations hold, the work supplies parameter-free closed-form expressions for QEC under two fundamental graph operations, directly extending the classical Schoenberg criterion without fitted parameters or self-referential reductions. The explicit computations for concrete families and the identification of new QE-class graphs strengthen the catalog of graphs whose Euclidean embeddability properties can be determined exactly. The lower bound for arbitrary Cartesian products and the extremal formulas for products with complete graphs further organize the landscape of quadratic embedding constants.

minor comments (4)
  1. Abstract: the notation “qec(G)” appears without prior definition; align it with the main-text definition of the quadratic embedding constant introduced via the Schoenberg criterion.
  2. Section 3 (join formulas): the statement of the general formula for G ∨ H when H is regular would be clearer if the precise eigenvalue relation used to verify positive-semidefiniteness of the adjusted distance matrix were displayed as a displayed equation rather than described in prose.
  3. Section 5 (applications): a compact table collecting the newly computed QEC values for the listed graph classes, together with the corresponding QE-class membership, would improve readability and allow immediate comparison with prior examples.
  4. Notation throughout: the symbol for the quadratic embedding constant should be introduced once in a dedicated notation paragraph and then used uniformly; occasional switches between “QEC” and inline math should be eliminated.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the manuscript. The recommendation for minor revision is noted, and we will prepare a revised version addressing any editorial or minor points.

Circularity Check

0 steps flagged

No significant circularity; derivations are self-contained

full rationale

The paper applies the classical Schoenberg criterion to the squared-distance matrices arising from the join and Cartesian product operations on graphs. The general formulas for QEC of G ∨ H (when H is regular or complete multipartite) and the lower bound for G □ H are obtained directly from eigenvalue relations and distance formulas under the stated assumptions of finite simple connected graphs. No load-bearing step reduces to a fitted parameter, self-citation chain, or redefinition of the target quantity; all expressions are derived from the graph operations themselves and the external Schoenberg positive-semidefiniteness condition. The results are therefore independent of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions from graph theory and the classical Schoenberg embedding criterion; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • domain assumption Graphs are finite, simple, and connected.
    Stated in the abstract as the setting for all results.
  • standard math QEC is defined via the classical Schoenberg criterion for Euclidean distance geometry.
    Invoked as the origin of the quantity being studied.

pith-pipeline@v0.9.0 · 5702 in / 1232 out tokens · 28897 ms · 2026-05-18T22:50:46.748282+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

19 extracted references · 19 canonical work pages

  1. [1]

    Baskoro, N

    E.T. Baskoro, N. Obata, Determining finite connected graphs along the quadratic embedding constants of paths . Electron. J. Graph Theory Appl. 9, 539-560 (2021)

    work page 2021

  2. [2]

    Bo˙ zejko,Positive-definite kernels, length functions on groups and non- commutative von Neumann inequality

    M. Bo˙ zejko,Positive-definite kernels, length functions on groups and non- commutative von Neumann inequality. Studia Math. 95, 107-118 (1989)

    work page 1989

  3. [3]

    Bo˙ zejko, T

    M. Bo˙ zejko, T. Januszkiewicz and R.J. Spatzier, Infinite Coxeter groups do not have Kazhdan’s property. J. Operator Theory 19, 63-67 (1988)

    work page 1988

  4. [4]

    Choudhury and R

    P.N. Choudhury and R. Nandi, Quadratic embedding constants of graphs: Bounds and distance spectra , Linear Algebra Appl. 680, 108-125 (2024)

    work page 2024

  5. [5]

    Graham and P.M

    R.L. Graham and P.M. Winkler, On isometric embedding of graphs. Trans. Amer. Math. Soc. 288, 527-536 (1985)

    work page 1985

  6. [6]

    Haagerup, An example of a nonnuclear C*-algebra which has the metric approximation property

    U. Haagerup, An example of a nonnuclear C*-algebra which has the metric approximation property. Invent. Math. 50, 289-293 (1979)

    work page 1979

  7. [7]

    Hora and N

    A. Hora and N. Obata, Quantum Probability and Spectral Analysis of Graphs , Springer, 2007

    work page 2007

  8. [8]

    Z. Lou, N. Obata and Q. Huang, Quadratic embedding constants of graph joins. Graphs Combin. 38 (2022), no. 5, Paper No. 161, 22 pp

    work page 2022

  9. [9]

    M lotkowski and N

    W. M lotkowski and N. Obata, Quadratic embedding constants of fan graphs and graph joins , Linear Algebra Appl. 709, 58-91 (2025). 18 PROJESH NATH CHOUDHURY AND RAJU NANDI

    work page 2025

  10. [10]

    M lotkowski, Quadratic embedding constants of path graphs

    W. M lotkowski, Quadratic embedding constants of path graphs. Linear Algebra Appl. 644, 95-107 (2022)

    work page 2022

  11. [11]

    M lotkowski and N

    W. M lotkowski and N. Obata, On quadratic embedding constants of star product graphs. Hokkaido Math. J. 49, 129-163 (2020)

    work page 2020

  12. [12]

    Obata, Primary non-QE graphs on six vertices

    N. Obata, Primary non-QE graphs on six vertices . Interdiscip. Inform. Sci. 29, 141-156 (2023)

    work page 2023

  13. [13]

    Obata, Complete multipartite graphs of non-QE class

    N. Obata, Complete multipartite graphs of non-QE class . Electron. J. Graph Theory Appl. 11, 511-527 (2023)

    work page 2023

  14. [14]

    Obata, Quadratic embedding constants of wheel graphs

    N. Obata, Quadratic embedding constants of wheel graphs . Interdiscip. Inform. Sci. 23, 171-174 (2017)

    work page 2017

  15. [15]

    Obata, Markov product of positive definite kernels and applications to Q-matrices of graph products

    N. Obata, Markov product of positive definite kernels and applications to Q-matrices of graph products. Colloq. Math. 122, 177-184 (2011)

    work page 2011

  16. [16]

    Obata, Positive Q-matrices of graphs

    N. Obata, Positive Q-matrices of graphs. Studia Math. 179, 81-97 (2007)

    work page 2007

  17. [17]

    Obata, A.Y

    N. Obata, A.Y. Zakiyyah, Distance matrices and quadratic embedding of graphs. Electron. J. Graph Theory Appl. 6, 37-60 (2018)

    work page 2018

  18. [18]

    Schoenberg, Metric spaces and positive definite functions

    I.J. Schoenberg, Metric spaces and positive definite functions . Trans. Amer. Math. Soc. 44, 522-536 (1938)

    work page 1938

  19. [19]

    Sur la definition axiomatique d’une classe d’espace dis- tancis vectoriellement applicable sur l’espace de Hilbert

    I.J. Schoenberg, Remarks to Maurice Frechet’s article “Sur la definition axiomatique d’une classe d’espace dis- tancis vectoriellement applicable sur l’espace de Hilbert” . Ann. of Math. 36, 724-732 (1935). (P.N. Choudhury) Department of Mathematics, Indian Institute of Technology Gandhinagar, Palaj, Gandhinagar 382355, India Email address: projeshnc@iitg...

    work page 1935