Analytic polyhedron: Difference between revisions
Jump to navigation
Jump to search
en>David Eppstein stub sort |
en>Mark viking Added boundary and a better definition of the Weil domain/polyhedron + ref verifying |
||
| Line 1: | Line 1: | ||
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 [[Glossary of graph theory#Subgraphs|subgraph]] [[graph isomorphism|isomorphic]] to ''G''. In this context, ''G'' is called a '''forbidden subgraph'''. <ref name=bollobas>''Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics'', [[Béla Bollobás]], 1986, ISBN 0-521-33703-8, [http://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]</ref> | |||
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 graph]]s <math>K_r,\, n\geq r \geq 3</math>. <ref>[http://books.google.com/books?id=4hWxnsLIfVAC&pg=PA254&dq=%22Turan-type+problem%22&lr= p. 254]</ref> | |||
An equivalent problem is how many edges in an ''n''-vertex graph guarantee that it has a subgraph isomorphic to ''G''?<ref>"Modern Graph Theory", by Béla Bollobás, 1998, ISBN 0-387-98488-7, [http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA123&dq=%22forbidden+subgraph+problem%22&lr=#PPA103,M1 p. 103]</ref> | |||
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 fom ''S''.<ref>Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels [http://books.google.com/books?id=C3tJsmWRQvkC&pg=PA590&dq=%22turan+number%22#PPA590,M1 p. 590]</ref> | |||
==See also== | |||
*[[Turán number]] | |||
*[[Subgraph isomorphism problem]] | |||
*[[Forbidden graph characterization]] | |||
*[[Zarankiewicz problem]] | |||
==References== | |||
{{reflist}} | |||
{{combin-stub}} | |||
[[Category:Extremal graph theory]] | |||
Revision as of 09:47, 30 September 2013
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 fom S.[4]
See also
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
- ↑ Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics, Béla Bollobás, 1986, ISBN 0-521-33703-8, p. 53, 54
- ↑ p. 254
- ↑ "Modern Graph Theory", by Béla Bollobás, 1998, ISBN 0-387-98488-7, p. 103
- ↑ Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels p. 590