Book Graph
The 👁 m
-book graph is defined as the graph
Cartesian product 👁 B_m=K_(1,m) square P_2
,
where 👁 K_(1,m)=S_(m+1)
is a star
graph, 👁 P_2
is the path graph on two nodes, and 👁 square
denotes the graph
Cartesian product. The generalization of the book graph to 👁 n
"stacked" pages may be called the 👁 (m,n)
-stacked book graph.
Special cases of the 👁 m
-book
graph are summarized below.
| 👁 m | graph |
| 1 | square graph |
| 2 | domino graph |
Precomputed properties of book graphs are implemented in the Wolfram Language as [👁 {
, m👁 }
].
The book graph 👁 B_n
is the simplex graph of the star
graph 👁 S_(n+1)=K_(1,n)
.
Book graphs of the form 👁 B_(4k+3)
do not satisfy the parity condition for gracefulness and hence are ungraceful
(Gallian 2018). Maheo (1980) proved that 👁 B_(2k)
is graceful and conjectured
that 👁 B_(4k+1)
is graceful for all positive
integer 👁 n
.
Delorme (1980) provided a simpler graceful labeling for 👁 B_(2k)
together with a graceful labeling for 👁 B_(4k+1)
, thus establishing the conjecture.
The book graph 👁 S_(n+1) square P_2
has chromatic polynomial, independence
polynomial, matching polynomial, and rank polynomial given by
![👁 (x-1)^(n-2)(x+1)^(n-2)[n^2x^2+(x^2-1)^3+n(-1+2x^2-2x^4)]](https://mathworld.wolfram.com/images/equations/BookGraph/Inline29.svg){kind=link}
![👁 ([1+3x(x+1)]^n(y-x)+x(y+1){1+x[3+x(3+y)]}^n)/y.](https://mathworld.wolfram.com/images/equations/BookGraph/Inline32.svg){kind=link}
The corresponding recurrence relations are
See also
Book Embedding, Book Thickness, Graph Cartesian Product, Stacked Book Graph, Star GraphExplore with Wolfram|Alpha
More things to try:
References
Delorme, D. "Two Sets of Graceful Graphs." J. Graph Th. 4, 247-250, 1980.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Oct. 30, 2025. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Maheo, M. "Strongly Graceful Graphs." Disc. Math. 29, 39-46, 1980.White, A. T. "Imbedding Problems in Graph Theory." Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, p. 49, 2001.Referenced on Wolfram|Alpha
Book GraphCite this as:
Weisstein, Eric W. "Book Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BookGraph.html