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

      0 references
      0 references
      0 references
      1983
      0 references
      Nordhaus-Gaddum type theorem
      0 references
      edge clique cover number
      0 references
      total clique cover number
      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

      Identifiers