论文标题
图形的结构化代码
Structured Codes of Graphs
论文作者
论文摘要
我们研究了一组基数$ n $上的图形家族的最大尺寸，以使该家族任意两个成员的边缘组的对称差异满足某些规定的状况。当规定的条件是连接性或$ 2 $ - 连接性，汉密尔顿性或固定恒星的遏制时，我们将完全解决$ n $的无限值解决问题。我们还研究了可以通过仅查看顶点集的子集来认证的当地情况。在这些情况下，定义了容量型渐近不变的渐近不变，并且当条件包含某个子图时，该不变式被证明是该必需子图的色数的简单函数。使用极端图理论的经典结果证明了这一点。考虑了几种变体，纸张以一系列开放问题结束。
We investigate the maximum size of graph families on a common vertex set of cardinality $n$ such that the symmetric difference of the edge sets of any two members of the family satisfies some prescribed condition. We solve the problem completely for infinitely many values of $n$ when the prescribed condition is connectivity or $2$-connectivity, Hamiltonicity or the containment of a spanning star. We also investigate local conditions that can be certified by looking at only a subset of the vertex set. In these cases a capacity-type asymptotic invariant is defined and when the condition is to contain a certain subgraph this invariant is shown to be a simple function of the chromatic number of this required subgraph. This is proven using classical results from extremal graph theory. Several variants are considered and the paper ends with a collection of open problems.
