×

On \(p\)-competition graphs of loopless Hamiltonian digraphs without symmetric arcs and graph operations. (English) Zbl 1501.05009

Summary: For a digraph \(D\), the \(p\)-competition graph \(C_p(D)\) of \(D\) is the graph satisfying the following: \(V(C_p(D))=V(D)\), for \(x,y\in V(C_p(D))\), \(xy\in E(C_p(D))\) if and only if there exist distinct \(p\) vertices \(v_1,v_2,\dots,v_p\in V(D)\) such that \(x\to v_i\), \(y\to v_i\in A(D)\) for each \(i=1,2,\dots,p\).
We show the \(H_1\cup H_2\) is a \(p\)-competition graph of a loopless digraph without symmetric arcs for \(p \ge 2\), where \(H_1\) and \(H_2\) are \(p\)-competition graphs of loopless digraphs without symmetric arcs and \(V(H_1)\cap V(H_2)=\{\alpha\}\). For \(p\)-competition graphs of loopless Hamiltonian digraphs without symmetric arcs, we obtain similar results. And we show that a star \(K_{1,n}\) is a \(p\)-competition graph of a loopless Hamiltonian digraph without symmetric arcs if \(n\ge 2p+3\) and \(p\ge 3\).
Based on these results, we obtain conditions such that spiders, caterpillars and cacti are \(p\)-competition graphs of loopless digraphs without symmetric arcs. We also obtain conditions such that these graphs are \(p\)-competition graphs of loopless Hamiltonian digraphs without symmetric arcs.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C45 Eulerian and Hamiltonian graphs
05C76 Graph operations (line graphs, products, etc.)