Universally signable graphs
Universally signable graphs
复制标题
通用可签名图
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Kristina Vuskovic
中科院分区：
文献类型：
--
作者：
M. Conforti;G. Cornuéjols;Ajai Kapoor;Kristina Vuskovic
在图中，长度大于3的无弦圈称为洞。设γ是一个{0，1}向量，其项与图G的孔一一对应。我们刻画了这样的图：对于向量γ的所有选择，我们可以选取图G的边集的一个子集F，使得|F∪H|эγH(Mod 2)对于所有Holesh OFG和|F∪T|э1对于所有Holesh OFG。我们称这些图形为泛可签署的。边子集F称为标号。所有其他的边都被贴上了标签。显然，对于所有向量γ的选择，没有洞的图(三角化图)在所有边上都可以用奇数标记来表示。我们给出了一个分解定理，它可以很好地刻画可泛可签的图。这是Hajal和Surányi[3]关于三角化图的一个定理的推广。
In a graph, a chordless cycle of length greater than three is called a hole. Let γ be a {0, 1} vector whose entries are in one-to-one correspondence with the holes of a graphG. We characterize graphs for which, for all choices of the vector γ, we can pick a subsetF of the edge set ofG such that |F ∪H| эγH (mod 2), for all holesH ofG and |F ∪T| э 1 for all trianglesT ofG. We call these graphsuniversally signable. The subsetF of edges is said to be labelledodd. All other edges are said to be labelledeven. Clearly graphs with no holes (triangulated graphs) are universally signable with a labelling of odd on all edges, for all choices of the vector γ. We give a decomposition theorem which leads to a good characterization of graphs that are universally signable. This is a generalization of a theorem due to Hajnal and Surányi [3] for triangulated graphs.