On weakly dense bases in a class of graphs (Q1859001)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On weakly dense bases in a class of graphs |
scientific article |
Statements
On weakly dense bases in a class of graphs (English)
0 references
17 February 2003
0 references
For any system of graphs \(B=\{ G_1,\dots,G_s\}\) let \(\rho_B\) denote its weight (i.e. the maximal number of edges). For any graph \(F\) its complexity \(l_B(F)\) is the minimal cardinality of coverings \(\{ H_1,\dots,H_m\}\) of \(F\), such that \(H_1,\dots ,H_m\) can be constructed from \(G_1,\dots ,G_s\) by identification of some nodes. The Shannon function of type II is defined as \[ l_B(q,p)=\max_{F: q(F)=q, p(F)=p} l_B(F) \] where \(q(F)\) is the number of edge and \(p(F)\) the number of nodes of \(F\). The system \(B=\{ G_1,\dots ,G_n\}\) is called a weakly dense basis (in the set of all connected graphs without loops and multiple edges), if the following asymptotic equality holds: \[ l_B(q,p)=\frac{q}{\rho_B}+o(p^2). \] The author proves the following criterion: a system \(B\) is a weakly dense basis if and only if it contains a bipartite graph with \(\rho_B\) edges.
0 references
Shannon function
0 references