No label defined (Q3313890)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3843787
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3843787 |
Statements
1983
0 references
Nordhaus-Gaddum type theorem
0 references
edge clique cover number
0 references
total clique cover number
0 references
0.8170123100280762
0 references
0.8129600286483765
0 references
0.8119844198226929
0 references
0.8064433336257935
0 references
[For the entire collection see Zbl 0523.00001.] Let G be a graph of order p, with complement \(\bar G\), and let f be a numerical function defined on the class of all graphs. A ''Nordhaus-Gaddum type'' theorem has the form \(\ell(p)\leq f(G)+f(\bar G)\leq u(p)\), \(L(p)\leq f(G)f(\bar G)\leq U(p)\). This paper develops such theorems for f giving the edge clique cover number \((f(G)=\theta_ 1(G)=the\) minimum number of cliques which include all edges of G) and for f giving the total clique cover number \((f(G)=\theta_ 2(G)=the\) minimum number of cliques which include all vertices and edges of G.) Sample result: for \(p\geq 2\), (a) \(1\leq \theta_ 1(G)+\theta_ 1(\bar G)\leq \frac{p(p-1)}{2}\); (b) 0\(\leq \theta_ 1(G)\theta_ 1(\bar G)\leq \frac{p^ 2(p-1)^ 2}{16}\); the lower bounds are sharp. The theorem derived for \(\theta_ 2\) (with p \(\geq 4)\) has only the product lower bound sharp, but when the authors restrict G to be bipartite (with \(p\geq 6)\), they obtain a theorem with all four bounds sharp (equality holding infinitely often.)
0 references