Издательство: | Книга по требованию |
Дата выхода: | июль 2011 |
ISBN: | 978-6-1306-8407-5 |
Объём: | 72 страниц |
Масса: | 129 г |
Размеры(В x Ш x Т), см: | 23 x 16 x 1 |
In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and one central vertex). A claw-free graph is a graph in which no induced subgraph is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the neighborhood of any vertex is the complement of a triangle-free graph. Claw-free graphs were initially studied as a generalization of line graphs, and gained additional motivation through three key discoveries about them: the fact that all such graphs have perfect matchings, the discovery of polynomial time algorithms for finding maximum independent sets in claw- free graphs, and the characterization of claw-free perfect graphs. They are the subject of hundreds of mathematical research papers and several surveys.
Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.