Antichain Graphs

A vertex u ∈ V₁ in a bipartite graph G(V₁ ∪ V₂, E) is redundant if all the vertices of V₂ that are adjacent to u are also adjacent to a vertex w (≠ u) in V₁. In other words, N_g(u) ⊆ N_G(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.