The \(m\)-step competition graph of a digraph
type: Item
instance of: scholarly article
title: The \(m\)-step competition graph of a digraph
zbMATH Open document ID: 0966.05066
DOI: 10.1016/S0166-218X(00)00214-6
author: Han Hyuk Cho
author: Suh-Ryung Kim
author: Yunsun Nam
published in: Discrete Applied Mathematics
publication date: 2001-08-12T00:00:00Z
review text: The authors define the \(m\)-step competition graph of a digraph and the \(m\)-step competition number \(k^m(G)\) of a graph \(G\) by applying natural generalizations of the well-known concepts of the competition graph of a digraph (\textit{F. S. Roberts} [Lect. Notes Math. 642, 477-490 (1978; Zbl 0389.90036)] and \textit{J. R. Lundgren} [IMA Vol. Math. Appl. 17, 221-243 (1989; Zbl 0701.92023)]) and of the competition number of a graph (\textit{Suh-Ryung Kim} [Ann. Discrete Math. 55, 313-326 (1993; Zbl 0789.05041)]). A characterization of the \(m\)-step competition graphs is obtained. It is shown that any path is a 2-step competition graph of a digraph and any spiked \(n\)-cycle is not the \(m\)-step competition graph of any digraph (for \(n\geq 4\) and \(m\geq 2\)). The 2-step competition numbers of cycles and paths are computed: \(k^2(C_3)=2,\) \(k^2(C_n)=4\) for \(n\geq 4\), and \(k^2(P_n)=2\) for any \(n\geq 2.\) Some open questions are included.
reviewed by: Matúš Harminc
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1512449
zbMATH Keywords: \(m\)-step competition graph
zbMATH Keywords: \(m\)-step competition number
zbMATH Keywords: digraph
zbMATH Keywords: characterization
zbMATH Keywords: cycles
zbMATH Keywords: paths
MaRDI profile type: Publication
cites work: Q4863414
cites work: Q4389779
cites work: Q5422499
cites work: Q5284004
cites work: Some recent results on niche graphs
cites work: Combinatorial matrix theory
cites work: Niche graphs
cites work: Primes in the semigroup of Boolean matrices
cites work: Prime Boolean matrices and factorizations
cites work: Q4393335
cites work: A characterization of competition graphs
cites work: Characterization of n-path graphs and of graphs having \(n\)-th root
cites work: Niche numbers
cites work: Competition graphs and clique dimensions
cites work: Inverting graphs of rectangular matrices
cites work: Q3758977
cites work: Q3797197
cites work: Q3139771
cites work: On the inequality \(dk(G)\leq k(G)+1\)
cites work: Q3113198
cites work: \(p\)-competition graphs
cites work: Q4940079
cites work: Q3479858
cites work: Chromatic numbers of competition graphs
cites work: Two-step graphs of trees
cites work: On the Computation of the Competition Number of a Graph
cites work: Q3689222
cites work: Q4171826
cites work: The competition-common enemy graph of a digraph
cites work: The double competition number of some triangle-free graphs
cites work: Q4028278
cites work: Q4304404
description: scientific article; zbMATH DE number 1512449