TOPICS
Search

Book Graph


BookGraph

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}].

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

pi(x)=(x-1)x(x^2-3x+3)^n
(1)
I(x)=2x(1+x)^n+(1+2x)^n
(2)
mu(x)=(x-1)^(n-2)(x+1)^(n-2)[n^2x^2+(x^2-1)^3+n(-1+2x^2-2x^4)]
(3)
R(x,y)=([1+3x(x+1)]^n(y-x)+x(y+1){1+x[3+x(3+y)]}^n)/y.
(4)

The corresponding recurrence relations are

pi_n(z)=(z^2-3z+3)pi_(n-1)(z)
(5)
I_n(x)=(3x+2)I_(n-1)(x)-(x+1)(2x+1)I_(n-2)(x)
(6)
mu_n(x)=3mu_(n-1)(x)-3mu_(n-2)(x)+mu_(n-3)(x)
(7)
R_n(x,y)=(x^2y+6x^2+6x+2)R_(n-1)(x,y)-(3x^2+3x+1)(x^2y+3x^2+3x+1)R_(n-2)(x,y).
(8)

See also

Graph Cartesian Product, Stacked Book Graph, Star Graph

Explore with Wolfram|Alpha

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

Cite this as:

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

Subject classifications