Book Graph


The m-book graph is defined as the graph Cartesian product B_m=S_(m+1) square P_2, where S_m is a star graph and P_2 is the path graph on two nodes. The generalization of the book graph to n "stacked" pages is the (m,n)-stacked book graph.

Special cases of the m-book graph are summarized below.

Precomputed properties of book graphs are implemented in the Wolfram Language as GraphData[{"Book", m}].

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


The corresponding recurrence relations are


See also

Graph Cartesian Product, Stacked Book Graph, Star Graph

Explore with Wolfram|Alpha


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. Dec. 21, 2018., 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 Graph

Cite this as:

Weisstein, Eric W. "Book Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications