Book Graph

The -book graph is defined as the graph Cartesian product , where is a star graph, is the path graph on two nodes, and denotes the graph Cartesian product. The generalization of the book graph to "stacked" pages may be called the -stacked book graph.

Special cases of the -book graph are summarized below.

	graph
1	square graph
2	domino graph

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

The book graph is the simplex graph of the star graph .

Book graphs of the form do not satisfy the parity condition for gracefulness and hence are ungraceful (Gallian 2018). Maheo (1980) proved that is graceful and conjectured that is graceful for all positive integer . Delorme (1980) provided a simpler graceful labeling for together with a graceful labeling for , thus establishing the conjecture.

The book graph has chromatic polynomial, independence polynomial, matching polynomial, and rank polynomial given by

			(1)
			(2)
			(3)
			(4)

The corresponding recurrence relations are

			(5)
			(6)
			(7)
			(8)