Connected triangle-free \(m\)-step competition graphs
type: Item
instance of: scholarly article
title: Connected triangle-free \(m\)-step competition graphs
zbMATH Open document ID: 1066.05120
author: Geir T. Helleloid
published in: Discrete Applied Mathematics
publication date: 2005-02-23T00:00:00Z
review text: Let \(D\) be a digraph, where from an ecological perspective \(D\) is a food web in which each vertex represents an organism and each arc represents a predator-prey relationship. Specifically, if \(x\) and \(u\) are vertices (organisms) in \(D\) and \(u\) is a prey of \(x\), then \(D\) ontains the arc \((x,u)\). If vertices \(x\) and \(y\) have a common prey, then they are in competition. The competition graph of \(D\), denoted by \(C(D)\), has the same vertex set as \(D\), and there is an edge between vertices \(x\) and \(y\) in \(C(D)\) when \(x\) and \(y\) are in competition in \(D\). And with that a directed walk of length \(k\) from a vertex \(v\) to a vertex \(w\) in a digraph consists of a sequence of vertices \((v_0,v_1,\dots, v_{k-1}, v_k)\), where \(v= v_0\) and \(w= v_k\), such that \((v_i, v_{i+1})\) is an arc in the digraph for each \(i\), \(0\leq i< k\); both vertices and arcs may occur multiple times in a directed walk. The \(m\)-step competition graph, which is a generalization of the competition graph, can be introduced in the following manner. Given a digraph \(D\), possibly containing loops, and some positive integer \(m\), we say that a vertex \(u\) is an \(m\)-step prey of a vertex \(x\) if there is a directed walk of length \(m\) from \(x\) to \(u\) in \(D\). Furthermore, \(u\) is an \(m\)-common prey of vertices \(x\) and \(y\) if \(u\) is an \(m\)-step prey of both \(x\) and \(y\). The \(m\)-step digraph \(D^m\) has the same vertex set as \(D\), and \((x,u)\) is an arc in \(D^m\) if \(u\) is an \(m\)-step prey of \(x\). The \(m\)-step competition graph of a digraph \(D\), denoted \(C^m(D)\), is defined to be \(C^m(D)= C(D^m)\); that means there is an edge between two vertices \(x\) and \(y\) in \(C^m(D)\) if and only if \(x\) and \(y\) have an \(m\)-step common prey in \(D\). (Special case \(m= 1\): \(C^1(D)= C(D)\).) It is already known from the literature that the paths \(P_n\) on \(n\) vertices are easily seen to be 1-step competition grap…
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 2137488
zbMATH Keywords: Competition graph
zbMATH Keywords: \(m\)-step competition number
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: j.dam.2004.06.010
OpenAlex ID: W2033092574
cites work: Combinatorial matrix theory
cites work: Q4393335
cites work: The \(m\)-step competition graph of a digraph
cites work: Characterization of n-path graphs and of graphs having \(n\)-th root
cites work: The \(m\)-step, same-step, and any-step competition graphs
cites work: Q3139771
cites work: Q3479858
cites work: Chromatic numbers of competition graphs
cites work: Two-step graphs of trees
cites work: Q4171826
DOI: 10.1016/J.DAM.2004.06.010
description: scientific article; zbMATH DE number 2137488