High Quality Content by WIKIPEDIA articles! In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Foldes and Hammer (1977a, 1977b), and independently introduced by Tyshkevich and Chernyak (1979). Note that the partition into a clique and an independent set need not be unique; for instance, the path a–b–c is a split graph, the vertices of which can be partitioned in three different ways: 1. the clique {a,b} and the independent set {c} 2. the clique {b,c} and the independent set {a} 3. the clique {b} and the independent set {a,c} Split graphs can be characterized in terms of their forbidden induced subgraphs: a graph is split if and only if no induced subgraph is a cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle).

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.