Top Qs
Timeline
Chat
Perspective

Book (graph theory)

From Wikipedia, the free encyclopedia

Book (graph theory)
Remove ads

In graph theory, a book graph (often written  ) may be any of several kinds of graph formed by multiple cycles sharing an edge.

Thumb
A triangular book

Variations

Summarize
Perspective

One kind, which may be called a quadrilateral book, consists of p quadrilaterals 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.[1][2] The 7-page book graph of this type provides an example of a graph with no harmonious labeling.[2]

A second type, which might be called a triangular book, is the complete tripartite graph K1,1,p. It is a graph consisting of triangles sharing a common edge.[3] A book of this type is a split graph. This graph has also been called a [4] or a thagomizer graph (after thagomizers, the spiked tails of stegosaurian dinosaurs, because of their pointy appearance in certain drawings) and their graphic matroids have been called thagomizer matroids.[5] Triangular books form one of the key building blocks of line perfect graphs.[6]

The term "book-graph" has been employed for other uses. Barioli[7] 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.)

Remove ads

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 contains as a subgraph.

  • If , then .[8]
  • 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) .[9]
Remove ads

References

Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads