Competition graphs induced by permutations

Original · EN

In prior work, Cho and Kim studied competition graphs arising from doubly partial orders. In this article, we consider a related problem where competition graphs are instead induced by permutations. We first show that this approach produces the same class of competition graphs as the doubly partial order. In addition, we observe that the 123 and 132 patterns in a permutation induce the edges in the associated competition graph. We classify the competition graphs arising from 132-avoiding permutations and show that those graphs must avoid an induced path graph of length 3. Finally, we consider the weighted competition graph of permutations and give some initial enumerative and structural results in that setting.