TOPICS
Search

Triangular Book Graph


A triangular book graph B_n consists of n>=1 triangles sharing one common graph edge. Equivalently, it is the graph join K_2+K_n^_ of a complete graph on two vertices and an empty graph on n vertices. It has n+2 vertices and 2n+1 edges. This is the book graph of the Ramsey number literature, distinct from the book graph K_(1,n) square P_2 formed from squares (Rousseau and Sheehan 1978).

For these triangular books, R(B_(n-1),B_n) is the least N such that every red-blue edge coloring of K_N contains a red B_(n-1) or a blue B_n. Chung and Wesley (2026) proved

 R(B_(n-1),B_n)=4n-1
(1)

whenever 2n-1 or n-1 is the order of a conference graph. In particular, either number may be a prime power congruent to 1 modulo 4. They also proved the equality when n=(Q+1)/2 for a prime power Q>3 with Q=3  (mod8), and when n=(r(r-1)+2)/4 for a prime power r>=7 with r=3  (mod4). Chung and Wesley (2026) report that an AI system assisted in discovering several of these constructions.

The off-diagonal asymptotics are now known for every fixed 0<alpha<=1. Dai et al. (2026) completed the determination of

 R(B_([alphan]),B_n)=(c(alpha)+o(1))n
(2)

as n->infty, where [x] is the ceiling function and

 c(alpha)={2   for 0<alpha<=1/6; 3/(1+2p_alpha^2)   for 1/6<alpha<=alpha_0; (1+sqrt(alpha))^2   for alpha_0<alpha<=1,
(3)

with alpha_0=(52-16sqrt(3))/121 and p_alpha=(1-sqrt(alpha(3-2alpha)))/(1-2alpha) in the middle range. Their new bounds resolve the interval 1/6<alpha<1/4. Dai et al. (2026) report that ChatGPT assisted with the arguments and computational exploration for their blocked-configuration approach.

Hu (2026) proved that for some absolute constant rho>0, every sufficiently large n-vertex simple graph with no B_k subgraph, for 2<=k<=rhon, contains at most q^(5-r)(q+1)^r copies of the cycle graph C_5, where n=5q+r and 0<=r<5. Equality holds precisely for balanced blow-ups of C_5.


See also

Book Graph, Ramsey Number

Explore with Wolfram|Alpha

References

Chung, S. and Wesley, W. J. "Constructions for Nearly Diagonal Book Ramsey Numbers." 27 Oct 2026. https://arxiv.org/abs/2610.36522.Dai, L.; Fan, C.; and Lin, Q. "The Asymptotics of Off-Diagonal Book Ramsey Numbers." 28 Oct 2026. https://arxiv.org/abs/2610.38515.House of Graphs. Triangular Book Graphs. Triangle K_3, Diamond Graph.Hu, W. "The Exact Number of Pentagons in Book-Free Graphs." 4 Nov 2026. https://arxiv.org/abs/2611.06753v1.Rousseau, C. C. and Sheehan, J. "On Ramsey Numbers for Books." J. Graph Th. 2, 77-87, 1978. https://doi.org/10.1002/jgt.3190020110.

Cite this as:

Weisstein, Eric W. "Triangular Book Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TriangularBookGraph.html

Subject classifications