A simple lower bound on edge coverings by cliques (Q807634): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q1844682 |
||
Property / reviewed by | |||
Property / reviewed by: B. Andrasfai / rank | |||
Revision as of 13:55, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A simple lower bound on edge coverings by cliques |
scientific article |
Statements
A simple lower bound on edge coverings by cliques (English)
0 references
1990
0 references
The edge clique-cover number c(G) is the minimum number of cliques which cover all edges in the undirected graph G. Call vertices x, y equivalent in the graph G with edge set E if xy\(\in E\) and for all vertices z different from x and y, zx\(\in E\) if and only if zy\(\in E\). In the present paper is proved: if a graph G has n vertices and G contains neither isolated vertices nor equivalent vertices then \(c(G)\geq \log_ 2(n+1)\).
0 references
edge covering
0 references
edge clique-cover number
0 references