The competition index of a nearly reducible Boolean matrix
Bull. Korean Math. Soc. 2013 Vol. 50, No. 6, 2001-2011
https://doi.org/10.4134/BKMS.2013.50.6.2001
Published online November 1, 2013
Han Hyuk Cho and Hwa Kyung Kim
Seoul National University, Sangmyung University
Abstract : Cho and Kim \cite{chokim} have introduced the concept of the competition index of a digraph. Similarly, the competition index of an $n \times n$ Boolean matrix $A$ is the smallest positive integer $q$ such that $A^{q+i}(A^T)^{q+i}$ $= A^{q+r+i}(A^T)^{q+r+i}$ for some positive integer $r$ and every nonnegative integer $i$, where $A^T$ denotes the transpose of $A$. In this paper, we study the upper bound of the competition index of a Boolean matrix. Using the concept of Boolean rank, we determine the upper bound of the competition index of a nearly reducible Boolean matrix.
Keywords : competition graph, $m$-step competition graph, competition index, competition period, scrambling index
MSC numbers : 05C20, 05C50
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd