Antichain Graphs

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


A vertex u ∈ V1 in a bipartite graph G(V1 ∪ V2, E) is redundant if all the vertices of V2 that are adjacent to u are also adjacent to a vertex w (≠ u) in V1. In other words, Ng(u) ⊆ NG(w). Such vertices increase the cost of the network (when it is a communication network) or increase the unnecessary membership of the network (when it is a social network). An ideal cost effective network is the one where there is no redundant vertex. In this article, we model the above type of networks using graphs and call them antichain graphs. We characterize such graphs and study their properties. We show that if G and H are antichain graphs then so is their cartesian product G × H. We design few more methods to construct new antichain graphs from the existing ones. We also present generating procedures, which generate some regular and biregular antichain graphs. We define a critical edge with reference to the antichain property. We also characterize the critical edge.

Original languageEnglish
Pages (from-to)1-7
Number of pages7
JournalIAENG International Journal of Applied Mathematics
Issue number3
Publication statusPublished - 2021

All Science Journal Classification (ASJC) codes

  • Applied Mathematics


Dive into the research topics of 'Antichain Graphs'. Together they form a unique fingerprint.

Cite this