2015/03/19 by Brian Nakamura, Nakamura, Brian, Elizabeth Yang +1
Computer Science · Mathematics · #05A05 #05A15 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05A05 #msc:05A15 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1503.05617
16 pages
arxiv created 2015/03/19 · openalex publication_date 2015/03/19 · arxiv updated 2015/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.