graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a book graph (often written

B_p

) may be any of several kinds of graph formed by multiple cycles sharing an edge.

Variations

One kind, which may be called a quadrilateral book, consists of ''p''

quadrilateral In geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''latus'', meaning "side". It is also called a tetragon, ...

s sharing a common edge (known as the "spine" or "base" of the book). That is, it is a Cartesian product of a star and a single edge. The 7-page book graph of this type provides an example of a graph with no harmonious labeling. A second type, which might be called a triangular book, is the complete tripartite graph ''K''_1,1,''p''. It is a graph consisting of

p

triangle A triangle is a polygon with three edges and three vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC. In Euclidean geometry, any three points, when non- colline ...

s sharing a common edge. A book of this type is a

split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by . A split graph may have m ...

. This graph has also been called a

K_e(2,p)

or a thagomizer graph (after

thagomizer A thagomizer () is the distinctive arrangement of four spikes on the tails of stegosaurine dinosaurs. These spikes are believed to have been a defensive measure against predators.Carpenter, K., Sanders, F., McWhinney, L., and Wood, L. 2005. Ev ...

s, the spiked tails of stegosaurian dinosaurs, because of their pointy appearance in certain drawings) and their

graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called ...

s have been called thagomizer matroids. Triangular books form one of the key building blocks of line perfect graphs. The term "book-graph" has been employed for other uses. Barioli used it to mean a graph composed of a number of arbitrary subgraphs having two vertices in common. (Barioli did not write

B_p

for his book-graph.)

Within larger graphs

Given a graph

G

, one may write

bk(G)

for the largest book (of the kind being considered) contained within

G

Theorems on books

Denote the Ramsey number of two triangular books by

r(B_p,\ B_q).

This is the smallest number

r

such that for every

r

-vertex graph, either the graph itself contains

B_p

as a subgraph, or its

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...

contains

B_q

as a subgraph. * If

1\leq p\leq q

, then

r(B_p,\ B_q)=2q+3

. * There exists a constant

c=o(1)

such that

r(B_p,\ B_q)=2q+3

whenever

q\geq cp

. * If

p\leq q/6+o(q)

, and

q

is large, the Ramsey number is given by

2q+3

. * Let

C

be a constant, and

k = Cn

. Then every graph on

n

vertices and

m

edges contains a (triangular)

B_k

References

{{DEFAULTSORT:Book (Graph Theory) Parametric families of graphs Planar graphs