论文标题
线性自由图
Linearly Free Graphs
论文作者
论文摘要
在本文中，我们对图形的内在属性感兴趣，该图是从它们的嵌入到Euclidean 3空间$ \ Mathbb {r}^3 $中的固有属性。如果将图形嵌入$ \ mathbb {r}^3 $中，则说是线性的，如果将每个边缘发送到行段。我们说，如果$π_1（\ Mathbb {r}^3-f（g））$是免费组，则嵌入$ g $的嵌入$ f $是$ \ mathbb {r}^3 $是免费的。最后，如果每个线性的嵌入都是免费的，则可以说一个简单的连接图是线性的。在1980年代，尼科尔森（Nicholson）证明了每个完整的图表是线性免费的。 在本文中，我们将尼科尔森的论点发展为一个一般概念，并建立了足够的条件，使线性嵌入是免费的。作为条件的应用，我们给出一个问题的部分答案：将完整的图形$ k_n $放大多少，以便保留线性的freeness且集团数量不会增加？并提供了一个支持我们答案的示例。 作为第二个应用程序，它表明，如果它的顶点少于8个顶点，则最小价值的简单连接图至少$ 3 $是线性免费的。有条件的不平等是严格的，因为我们找到了一个$ 8 $顶点的图形，该图形不是线性免费的。还证明，对于$ n，m \ leq 6 $，完整的两部分图$ k_ {n，m} $是线性免费的。
In this paper we are interested in an intrinsic property of graphs which is derived from their embeddings into the Euclidean 3-space $\mathbb{R}^3$. An embedding of a graph into $\mathbb{R}^3$ is said to be linear, if it sends every edge to be a line segment. And we say that an embedding $f$ of a graph $G$ into $\mathbb{R}^3$ is free, if $π_1(\mathbb{R}^3-f(G))$ is a free group. Lastly a simple connected graph is said to be linearly free if every its linear embedding is free. In 1980s it was proved that every complete graph is linearly free, by Nicholson. In this paper, we develop Nicholson's arguments into a general notion, and establish a sufficient condition for a linear embedding to be free. As an application of the condition we give a partial answer for a question: how much can the complete graph $K_n$ be enlarged so that the linear freeness is preserved and the clique number does not increase? And an example supporting our answer is provided. As the second application it is shown that a simple connected graph of minimal valency at least $3$ is linearly free, if it has less than 8 vertices. The conditional inequality is strict, because we found a graph with $8$ vertices which is not linearly free. It is also proved that for $n, m \leq 6$ the complete bipartite graph $K_{n,m}$ is linearly free.
