关于独立数为2的图的边团覆盖数

Edge Clique Cover Number of Graphs with Independence Number Two

摘要: 设G为一个图。图的边团覆盖是指由若干团构成的集合，满足该集合能覆盖图所有的边。图G的边团覆盖数，是指使得G存在基数为k的边团覆盖的最小正整数k。关于边团覆盖数的上界，学界曾提出如下猜想：对任意满足独立数为2的图G，均有边团覆盖数小于等于n。若一个图G满足独立数为k，且对G的任意一条边e，删掉这条边后独立数增大，则称G为独立数为k的临界图。本文聚焦于独立数为2的临界图，并证明下述结论：若G是不含5个点的轮图的独立数为2的临界图，则对任意以G为支撑子图的图，满足图G的边团覆盖数小于等于n + 1。

Abstract: Let G be a graph. An edge clique cover of the graph refers to a collection of several cliques, such that the collection can cover all edges of the graph. An edge clique cover of the graph refers to a collection of several cliques, such that the collection can cover all edges of the graph. The edge clique cover number of graph G is the smallest positive integer k for which there exists an edge clique cover of for which there exists an edge clique cover of G with cardinality k. Regarding the upper bound of the edge clique cover number, the following conjecture has been proposed in academic circles: for any graph G with independence number 2, its edge clique cover number is less than or equal to n . If a graph G has an independence number of k, and for any edge e of G, the independence number increases after deleting this edge, then G is called a critical graph with independence number k. This paper focuses on critical graphs with independence number 2 and proves the following conclusion: if G is a critical graph with independence number 2 that does not contain the 5-vertex wheel graph, then for any graph taking G as its spanning subgraph, the edge clique cover number of graph G is less than or equal to n + 1.