“Forbidden subgraph problem”的意思、由来-开放百科全书

词条

Forbidden subgraph problem

释义

See also
References

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph G, find the maximal number of edges in an n-vertex graph which does not have a subgraph isomorphic to G. In this context, G is called a forbidden subgraph.^[1]

It is also called the Turán-type problem and the corresponding number is called the Turán number for graph G. It is called so in memory of Pál Turán, who determined this number for all n and all complete graphs .^[2]

An equivalent problem is how many edges in an n-vertex graph guarantee that it has a subgraph isomorphic to G?^[3]

The problem may be generalized for a set of forbidden subgraphs S: find the maximal number of edges in an n-vertex graph which does not have a subgraph isomorphic to any graph form S.^[4]

References

1. ^Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics, Béla Bollobás, 1986, {{ISBN|0-521-33703-8}}, [https://books.google.com/books?id=LUUrTJ1Cx_0C&pg=PA53&lpg=PA53&dq=%22forbidden+subgraph+problem%22&source=bl&ots=o_ZcOV93Ep&sig=70mXvYYMHyDSGdmOIwpHMLpx86E&hl=en&ei=n3KjSfHMCInOsAOCttieAg&sa=X&oi=book_result&resnum=7&ct=result#PPA54,M1 p. 53, 54]
2. ^[https://books.google.com/books?id=4hWxnsLIfVAC&pg=PA254&dq=%22Turan-type+problem%22&lr= p. 254]
3. ^"Modern Graph Theory", by Béla Bollobás, 1998, {{ISBN|0-387-98488-7}}, [https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA123&dq=%22forbidden+subgraph+problem%22&lr=#PPA103,M1 p. 103]
4. ^Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels [https://books.google.com/books?id=C3tJsmWRQvkC&pg=PA590&dq=%22turan+number%22#PPA590,M1 p. 590]

1 : Extremal graph theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

See also

References