Related Families of Graphs
The Colin de Verdière graph invariant is an integer defined for any graph using algebraic graph theory. The graphs with Colin de Verdière graph invariant at most μ, for any fixed constant μ, form a minor-closed family, and the first few of these are well-known: the graphs with μ ≤ 1 are the linear forests (disjoint unions of paths), the graphs with μ ≤ 2 are the outerplanar graphs, and the graphs with μ ≤ 3 are the planar graphs. As Robertson, Seymour & Thomas (1993a) conjectured and Lovász & Schrijver (1998) proved, the graphs with μ ≤ 4 are exactly the linklessly embeddable graphs.
The planar graphs and the apex graphs are linklessly embeddable, as are the graphs obtained by Y-Δ transforms from these graphs. The YΔY reducible graphs are the graphs that can be reduced to a single vertex by Y-Δ transforms, removal of isolated vertices and degree-one vertices, and compression of degree-two vertices; they are also minor-closed, and include all planar graphs. However, there exist linkless graphs that are not YΔY reducible, such as the apex graph formed by connecting an apex vertex to every degree-three vertex of a rhombic dodecahedron. There also exist linkless graphs that cannot be transformed into an apex graph by Y-Δ transforms, removal of isolated vertices and degree-one vertices, and compression of degree-two vertices: for instance, the ten-vertex crown graph has a linkless embedding, but cannot be transformed into an apex graph in this way.
Related to the concept of linkless embedding is the concept of knotless embedding, an embedding of a graph in such a way that none of its simple cycles form a nontrivial knot. The graphs that do not have knotless embeddings include K7 and K3,3,1,1. However, there also exist minimal forbidden minors for knotless embedding that are not formed (as these two graphs are) by adding one vertex to an intrinsically linked graph.
One may also define graph families by the presence or absence of more complex knots and links in their embeddings, or by linkless embedding in three-dimensional manifolds other than Euclidean space. Flapan, Naimi & Pommersheim (2001) define a graph embedding to be triple linked if there are three cycles no one of which can be separated from the other two; they show that K9 is not intrinsically triple linked, but K10 is. More generally, one can define an n-linked embedding for any n to be an embedding that contains an n-component link that cannot be separated by a topological sphere into two separated parts; minor-minimal graphs that are intrinsically n-linked are known for all n.
Read more about this topic: Linkless Embedding
Famous quotes containing the words related and/or families:
“No being exists or can exist which is not related to space in some way. God is everywhere, created minds are somewhere, and body is in the space that it occupies; and whatever is neither everywhere nor anywhere does not exist. And hence it follows that space is an effect arising from the first existence of being, because when any being is postulated, space is postulated.”
—Isaac Newton (1642–1727)
“The authoritarian child-rearing style so often found in working-class families stems in part from the fact that parents see around them so many young people whose lives are touched by the pain and delinquency that so often accompanies a life of poverty. Therefore, these parents live in fear for their children’s future—fear that they’ll lose control, that the children will wind up on the streets or, worse yet, in jail.”
—Lillian Breslow Rubin (20th century)