Every finite graph is a full subgraph of a rigid graph |
| |
| Authors: | V Chvátal P Hell L Ku?era J Nešet?il |
| |
| Institution: | 1. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada;2. Département des Mathématiques, Université de Montréal, Montréal, Quebec, Canada;3. Matematicko-fyzikální fakulta University Karlovy, Prague, Czechoslovakia |
| |
| Abstract: | We prove that every finite undirected graph is a full subgraph of a rigid graph. Our construction proceeds on taking a family of “mutually rigid” graphs and attaching them to the vertices of a given graph in a one-to-one manner; then the vertices are fixed on their place. Actually, the new graph is “strongly rigid”, which enables us to show that the category of all graphs containing a given finite graph as a full subgraph is binding. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
