Generalized complements of a graph

E. Sampathkumar, L. Pushpa Latha, C. V. Venkatachalam, Pradeep Bhat

Research output: Contribution to journalArticlepeer-review

28 Citations (Scopus)


Let G = (V, E) be a graph and P = {V1, V2, ..., Vk} be a partition of V of order k ≥ 1. For each set Vr in P, remove the edges of G inside Vr and add the edges Ḡ, (the complement of G) joining the vertices Vr. The graph GPk (i) thus obtained is called the k(i)-complement of G with respect to P. The graph G is k(i)-self complementary (k(i)-s.c) if GPk (i) ≅ G for some partition P of V of order k. Further, G is k(i)co-self complementary (k(i)-co-s.c.) if GPk(i) ≅ Ḡ. We determine (1) all k(i)-s.c trees for k = 2, 3, and (2) 2(i)-s.c. unicyclic graphs. Also, some necessary conditions for a tree/unicyclic graph to be k(i)-s.c. are obtained. We indicate how to obtain characterizations of all k(i)-co.s.c. trees, unicyclic graphs and forests from known results.

Original languageEnglish
Pages (from-to)625-639
Number of pages15
JournalIndian Journal of Pure and Applied Mathematics
Issue number6
Publication statusPublished - 01-06-1998

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics


Dive into the research topics of 'Generalized complements of a graph'. Together they form a unique fingerprint.

Cite this