“Book (graph theory)”的意思、由来-开放百科全书

In graph theory, 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 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 K_1,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] Triangular books form one of the key building blocks of line perfect graphs.^[5]

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

as a subgraph.

References

1. ^{{mathworld|id=BookGraph|title=Book Graph}}
2. ^¹{{cite journal | last = Gallian | first = Joseph A. | author-link = Joseph Gallian | journal = Electronic Journal of Combinatorics | mr = 1668059 | page = Dynamic Survey 6 | title = A dynamic survey of graph labeling | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6 | volume = 5 | year = 1998}}
3. ^{{cite journal |author=Lingsheng Shi |author2=Zhipeng Song |title=Upper bounds on the spectral radius of book-free and/or K_2,l-free graphs |journal=Linear Algebra and its Applications |volume=420 |year=2007 |pages=526–9 |doi=10.1016/j.laa.2006.08.007}}
4. ^{{cite journal|last=Erdős|first=Paul|year=1963|title=On the structure of linear graphs|journal=Israel Journal of Mathematics|volume=1|pages=156–160|authorlink=Paul Erdős|doi=10.1007/BF02759702}}
5. ^{{cite journal | last = Maffray | first = Frédéric | doi = 10.1016/0095-8956(92)90028-V | issue = 1 | journal = Journal of Combinatorial Theory | mr = 1159851 | pages = 1–8 | series = Series B | title = Kernels in perfect line-graphs | volume = 55 | year = 1992}}.
6. ^{{cite journal |first=Francesco |last=Barioli |title=Completely positive matrices with a book-graph |journal=Linear Algebra and its Applications |volume=277 |year=1998 |pages=11–31 |doi=10.1016/S0024-3795(97)10070-2}}
7. ^{{cite journal | last1 = Rousseau | first1 = C. C. | author1-link = Cecil C. Rousseau | last2 = Sheehan | first2 = J. | doi = 10.1002/jgt.3190020110 | issue = 1 | journal = Journal of Graph Theory | mr = 486186 | pages = 77–87 | title = On Ramsey numbers for books | volume = 2 | year = 1978}}
8. ^{{cite journal |first=P. |last=Erdős |url=http://projecteuclid.org/euclid.ijm/1255631811 |title=On a theorem of Rademacher-Turán |journal=Illinois Journal of Mathematics |volume=6 |year=1962 |pages=122–7}}