Upper bounds on the edge clique cover number of a graph (Q799696): Difference between revisions

For graphs without loops and multiple edges, let n be the number of nodes, k be the minimum number of cliques required to cover all the nodes, \(\bar k\) be the minimum number of cliques required to cover all the edges, p be the minimum number of nodes such that every edge is incident with at least one of them, P be the maximum number of nodes such that no two are adjacent and E be the maximum number of edges such that no two are adjacent. The authors show that \(\bar k>pP\) for almost all graphs and present several sufficient conditions for \(\bar k\leq pP\) to hold moreover they prove the following inequalities: \(\bar k\leq k(n-k)\) and \(\bar k\leq E(n-E).\)