The $p$-Competition Graphs of Strongly Connected and Hamiltonian Digraphs

Abstract

Competition graphs were first introduced by Joel Cohen in the study of food webs and have since been extensively studied. Graphs which are the competition graph of a strongly connected or Hamiltonian digraph are of particular interest in applications to communication networks. It has been previously established that every graph without isolated vertices (except $K_2$) which is the competition graph of a loopless digraph is also the competition graph of a strongly connected digraph. We establish an analogous result for one generalization of competition graphs, the $p$-competition graph. Furthermore, we establish some large classes of graphs, including trees, as the $p$-competition graph of a loopless Hamiltonian digraph and show that interval graphs on $n\ge 4$ vertices are the $2$-competition graphs of loopless Hamiltonian digraphs.