Extremal clique coverings of complementary graphs

D. de Caen; P. Erdos; N. J. Pullmann; N. C. Wormald

doi:10.1007/BF02579256

Extremal clique coverings of complementary graphs

D. de Caen, P. Erdos, N. J. Pullmann, N. C. Wormald

Research output: Contribution to journal › Article › Research › peer-review

7 Citations (Scopus)

Abstract

Let cc(G) (resp. cp(G)) be the least number of complete subgraphs needed to cover (resp. partition) the edges of a graph G. We present bounds on max {cc(G)+cc(Ḡ)}, max {cp(G)+cp(Ḡ)}, max {cc(G)cc(Ḡ)} and max {cp(G)cp(Ḡ)} where the maxima are taken over all graphs G on n vertices and Ḡ is the complement of G in K_n . Several related open problems are also given.

Original language	English
Pages (from-to)	309-314
Number of pages	6
Journal	Combinatorica
Volume	6
Issue number	4
DOIs	https://doi.org/10.1007/BF02579256
Publication status	Published - Dec 1986
Externally published	Yes

Keywords

AMS subject classification (1980): 05C35

Access to Document

10.1007/BF02579256

Cite this

@article{b07eda0b28a44b64a38c352476ca728a,

title = "Extremal clique coverings of complementary graphs",

abstract = "Let cc(G) (resp. cp(G)) be the least number of complete subgraphs needed to cover (resp. partition) the edges of a graph G. We present bounds on max {cc(G)+cc(Ḡ)}, max {cp(G)+cp(Ḡ)}, max {cc(G)cc(Ḡ)} and max {cp(G)cp(Ḡ)} where the maxima are taken over all graphs G on n vertices and Ḡ is the complement of G in K n . Several related open problems are also given.",

keywords = "AMS subject classification (1980): 05C35",

author = "{de Caen}, D. and P. Erdos and Pullmann, {N. J.} and Wormald, {N. C.}",

year = "1986",

month = dec,

doi = "10.1007/BF02579256",

language = "English",

volume = "6",

pages = "309--314",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - Extremal clique coverings of complementary graphs

AU - de Caen, D.

AU - Erdos, P.

AU - Pullmann, N. J.

AU - Wormald, N. C.

PY - 1986/12

Y1 - 1986/12

N2 - Let cc(G) (resp. cp(G)) be the least number of complete subgraphs needed to cover (resp. partition) the edges of a graph G. We present bounds on max {cc(G)+cc(Ḡ)}, max {cp(G)+cp(Ḡ)}, max {cc(G)cc(Ḡ)} and max {cp(G)cp(Ḡ)} where the maxima are taken over all graphs G on n vertices and Ḡ is the complement of G in K n . Several related open problems are also given.

AB - Let cc(G) (resp. cp(G)) be the least number of complete subgraphs needed to cover (resp. partition) the edges of a graph G. We present bounds on max {cc(G)+cc(Ḡ)}, max {cp(G)+cp(Ḡ)}, max {cc(G)cc(Ḡ)} and max {cp(G)cp(Ḡ)} where the maxima are taken over all graphs G on n vertices and Ḡ is the complement of G in K n . Several related open problems are also given.

KW - AMS subject classification (1980): 05C35

UR - http://www.scopus.com/inward/record.url?scp=51649157071&partnerID=8YFLogxK

U2 - 10.1007/BF02579256

DO - 10.1007/BF02579256

M3 - Article

AN - SCOPUS:51649157071

SN - 0209-9683

VL - 6

SP - 309

EP - 314

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

Extremal clique coverings of complementary graphs

Abstract

Keywords

Access to Document

Other files and links

Cite this