In
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 conne ...
, a book graph (often written
) 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
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
of a
star
A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...
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
triangle
A triangle is a polygon with three Edge (geometry), edges and three Vertex (geometry), 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, an ...
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
or a thagomizer graph (after
thagomizer
A thagomizer () is the distinctive arrangement of four spikes on the tails of Stegosauridae, stegosaurine dinosaurs. These spikes are believed to have been a defensive measure against predators.Carpenter, K., Sanders, F., McWhinney, L., and Woo ...
s, the spiked tails of
stegosauria
Stegosauria is a group of herbivorous ornithischian dinosaurs that lived during the Jurassic and early Cretaceous periods. Stegosaurian fossils have been found mostly in the Northern Hemisphere, predominantly in what is now North America, Europe, ...
n 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 co- ...
s have been called thagomizer matroids. Triangular books form one of the key building blocks of
line perfect graph
In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle.
A graph is line perfect if and only if each of its biconnected compon ...
s.
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
for his book-graph.)
Within larger graphs
Given a graph
, one may write
for the largest book (of the kind being considered) contained within
.
Theorems on books
Denote the
Ramsey number of two triangular books by
This is the smallest number
such that for every
-vertex graph, either the graph itself contains
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 a ...
contains
as a subgraph.
* If
, then
.
* There exists a constant
such that
whenever
.
* If
, and
is large, the
Ramsey number is given by
.
* Let
be a constant, and
. Then every graph on
vertices and
edges contains a (triangular)
.
References
{{DEFAULTSORT:Book (Graph Theory)
Parametric families of graphs
Planar graphs