Upper bounds on the edge clique cover number of a graph (Q799696): Difference between revisions
From MaRDI portal
Latest revision as of 15:40, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper bounds on the edge clique cover number of a graph |
scientific article |
Statements
Upper bounds on the edge clique cover number of a graph (English)
0 references
1984
0 references
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).\)
0 references
clique covers
0 references