论文标题
分数超图同构和分数不变性
Fractional hypergraph isomorphism and fractional invariants
论文作者
论文摘要
分数图同构是图形同构的整数编程公式的线性松弛。它保留了一些不变的图形，例如度序列和公平分区，但并不保留其他诸如连接性，集团和独立性数字，变色数，顶点和边缘封面数字，匹配数，统治和总统治数等其他图形。 在这项工作中，我们将分数同构的概念扩展到了超图，并给出了另一种表征，类似于图形已知的一个。通过这个新概念，我们证明了超图上的分数堆积，覆盖，匹配和横向数是在分数超图同构下不变的。结果，在分数图同构下，分数匹配，顶点和边缘盖，独立性，统治和总统治数是不变的。这不是分数色，集团和集团覆盖数的情况。这样，大多数经典的分数参数在分数图等构象下的不变性进行了分类。
Fractional graph isomorphism is the linear relaxation of an integer programming formulation of graph isomorphism. It preserves some invariants of graphs, like degree sequences and equitable partitions, but it does not preserve others like connectivity, clique and independence numbers, chromatic number, vertex and edge cover numbers, matching number, domination and total domination numbers. In this work, we extend the concept of fractional graph isomorphism to hypergraphs, and give an alternative characterization, analogous to one of those that are known for graphs. With this new concept we prove that the fractional packing, covering, matching and transversal numbers on hypergraphs are invariant under fractional hypergraph isomorphism. As a consequence, fractional matching, vertex and edge cover, independence, domination and total domination numbers are invariant under fractional graph isomorphism. This is not the case of fractional chromatic, clique, and clique cover numbers. In this way, most of the classical fractional parameters are classified with respect to their invariance under fractional graph isomorphism.
