Abstract
For any positive integers k and m, the k-step m-competition graph C k m (D) of a digraph D has the same set of vertices as D and there is an edge between vertices x and y if and only if there are distinct m vertices v1, v2, · · ·, v m in D such that there are directed walks of length k from x to v i and from y to v i for all 1 ≤ i ≤ m. The m-competition index of a primitive digraph D is the smallest positive integer k such that C k m (D) is a complete graph. In this paper, we obtained some sharp upper bounds for the m-competition indices of various classes of primitive digraphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Akelbek, M., Kirkland, S. Coefficients of ergodicity and the scrambling index. Linear Algebra Appl., 430: 1111–1130 (2009)
Akelbek, M., Kirkland, S. Primitive digraphs with the largest scrambling index. Linear Algebra Appl., 430: 1099–1110 (2009)
Akelbek, M., Fital, S., Shen, J. A bound on the scrambling index of a primitive matrix using Boolean rank. Linear Algebra Appl., 431: 1923–1931 (2009)
Brualdi, R.A., Ryser, H.J. Combinatorial Matrix Theory. Cambridge University Press, Cambridge, 1991
Bondy, J.A., Murty, U.S.R. Graph Theory with Applications. North-Holland, New York, 1976
Cho, H.H., Kim, S.R., Nam, Y. The m-step competition graph of digraph. Discrete Appl. Math., 105: 115–127 (2000)
Cho, H.H., Kim, H.K. Competition indices of digraphs. In: Proceedings of Workshop in Combinatorices, 2004, 99–107
Chen, S.X., Liu, B.L. The scrambling index of symmetric primitive matrices. Linear Algebra Appl., 433: 1110–1126 (2010)
Cohen, J.E. Food Webs and Niche Space. Princeton University Press, Princeton, NJ,1978
Huang, Y.F., Liu, B.L. Generalized scrambling indices of a primitive digraph. Linear Algebra Appl., 433: 1798–1808 (2010)
Kim, H.K. Competition indices of tournaments. Bull. Korean Math. Soc., 45: 385–396 (2008)
Kim, H.K. Generalized competition index of a primitive digraph. Linear Algebra Appl., 433: 72–79 (2010)
Kim, H.K. A bound on the generalized competition index of a primitive matrix using Boolean rank. Linear Algebra Appl., 435: 2166–2174 (2011)
Kim, H.K., Lee, S.H. Generalized competition indices of symmetric primitive digraphs. Discrete Appl. Math., 160: 1583–1590 (2012)
Kim, H.K., Park, S.G. A bound of generalized competition index of a primitive digraph. Linear Algebra Appl., 436: 86–98 (2012)
Kim, H.K. Generalized competition index of an irreducible Boolean matrix. Linear Algebra Appl., 438: 2747–2756 (2013)
Kim, H.K. Scrambling index set of primitive digraphs. Linear Algebra Appl., 439: 1886–1893 (2013)
Kim, H.K. Characterization of irreducible Boolean matrices with the largest generalized competition index. Linear Algebra Appl., 466: 218–232 (2015)
Kim, S.R. Competition graphs and scientific laws for food webs and other systems. PH.D. Thesis, Rutgers University, 1988
Liu, B.L. On fully indecoposable exponent for primitive Boolean matrices symmetric ones. Linear Multilinear Algebra., 31: 131–138 (1992)
Liu, B.L., Lai, H.J. Matrices in Combinatorics and Graph Theory. Kluwer Academic Publishers, 2000
Liu, B.L., Huang, Y.F. The scrambling index of primitive digraphs. Comput. Math. Appl., 60: 706–721 (2010)
Moon, J.W., Moser, L. Almost all (0, 1)-matrices are primitive. Studia Scient. Math. Hung., 1: 153–156 (1966)
Shao, J.Y. On the exponent set of symmetric primitive matrices. Sci. Sinica Ser. A., 9: 931–939 (1986)
Shao, Y.L., Gao, Y.B. The primitive Boolean matrices with the second largest scrambling index by Boolean rank. Czechoslovak Mathematical J., 64 (139): 269–283 (2014)
Shao, Y.L., Gao, Y.B. The scrambling index set of primitive minimally strong digraphs. Linear Algebra Appl., 500: 1–14 (2016)
Shen, J., Gregory, D., Neufeld, S. Exponents of indecomposability. Linear Algebra Appl., 288: 229–241 (1999)
Sim, M.S., Kim, H.K. On generalized competition index of a primitive tournament. Discrete Math., 311: 2657–2662 (2011)
You, L.H., Liu, B.L., Shen, J. r-indecomposable and r-nearly decomposable matrices. Linear Algebra Appl., 407: 105–116 (2005)
Zhang L., Huang, T.Z. Bounds on the generalized µ-scrambling indices of primitive digraphs. International Journal of Computer Mathematics, 89: 17–29 (2012)
Zhou, B. On the common consequent indices of nearly reducible binary relations. Util. Math., 56: 233–243 (1999)
Zhou, B., Liu, B.L. New results on the common consequent index of a binary relation. European J. Combin., 21: 167–179 (2000)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the National Natural Science Foundation of China (No. 11571123, 11671156) and the Guangdong Provincial Natural Science Foundation (Grant No. 2015A030313377).
Rights and permissions
About this article
Cite this article
You, Lh., Chen, F., Shen, J. et al. Generalized competition index of primitive digraphs. Acta Math. Appl. Sin. Engl. Ser. 33, 475–484 (2017). https://doi.org/10.1007/s10255-017-0675-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-017-0675-0