A simple lower bound on edge coverings by cliques (Q807634)
From MaRDI portal
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