2024/05/22 by Choi, Myungho, Chu, Hojin, Kim, Suh-Ryung
#05C20 #05C75 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2405.13363
The competition-common enemy graph (CCE graph) of a digraph D is the graph with the vertex set V(D) and an edge uv if and only if u and v have a common predator and a common prey in D. If each vertex of a digraph D has indegree at most i and outdegree at most j, then D is called an ⟨ i,j ⟩ digraph. In this paper, we fully characterize the CCE graphs of ⟨ 2,2⟩ digraphs. Then we investigate the CCE graphs of acyclic ⟨ 2,2 ⟩ digraphs, and prove that any CCE graph of an acyclic ⟨ 2,2 ⟩ digraph with at most seven components is interval, and the bound is sharp. While characterizing acyclic ⟨ 2,2 ⟩ digraphs that have interval graphs as their competition graphs, Hefner~\it et al. (1991) initiated the study of competition graphs of degree-bounded digraphs. Recently, Lee~\em et al. (2017) and Eoh and Kim (2021) studied phylogeny graphs of degree-bounded digraphs to extend their work.