A Class of Primitive Two-Colored Digraph with Large Competition Index
DOI:
10.33395/sinkron.v8i3.12744Keywords:
Digraph, primitive digraphs, primitive two-colored digraph D^2Abstract
The competition index of a primitive two-colored digraph D^2, denoted k(D^((2))), is the smallest positive integer h+l such that for each pair of vertices u and v there is vertex w with the property that there is a (h,l)-walk from v to w. For two-colored digraph on n vertices it is known that k(D^((2) ))≤(3n^3+2n^2-2n)/2. In this work, we discuss a class of primitive two-colored digraph consisting of two cycles whose scrambling index closes to (3n^3+2n^2-2n)/2
Downloads
References
Akelbek, M., & Kirkland, S. (2009a). Coefficients of ergodicity and the scrambling index. Linear Algebra and Its Applications, 430(4), 1111–1130.
Akelbek, M., & Kirkland, S. (2009b). Primitive digraphs with the largest scrambling index. Linear Algebra and Its Applications, 430(4), 1099–1110.
Fornasini, E., & Valcher, M. E. (1998a). Multidimensional systems with finite support behaviors: Signal structure, generation, and detection. SIAM Journal on Control and Optimization, 36(2), 760–779.
Fornasini, E., & Valcher, M. E. (1998b). Primitivity of positive matrix pairs: algebraic characterization, graph theoretic description, and 2D systems interpretation. SIAM Journal on Matrix Analysis and Applications, 19(1), 71–88.
Gao, Y., & Shao, Y. (2005). Exponents of two-colored digraphs with two cycles. Linear Algebra and Its Applications, 407, 263–276.
Hussein, I., Prasetyo, Y. D., & Suwilo, S. (2014). Upper generalized exponents of two-colored primitive extremal ministrong digraphs. AIP Conference Proceedings, 1635(1), 430–439.
Kim, H. K., & Lee, S. H. (2012). Generalized competition indices of symmetric primitive digraphs. Discrete Applied Mathematics, 160(10–11), 1583–1590.
Mahlmann, P., & Schindelhauer, C. (2006). Distributed random digraph transformations for peer-to-peer networks. Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 308–317.
Shader, B. L., & Suwilo, S. (2003). Exponents of nonnegative matrix pairs. Linear Algebra and Its Applications, 363, 275–293.
Suwilo, S., & Shader, B. L. (2006). On 2-exponents of ministrong 2-digraphs. Pure Mathematics, 51.
Syahmarani, A., & Suwilo, S. (2012). Vertex exponents of a class of two-colored hamiltonian digraphs. Journal of the Indonesian Mathematical Society, 1–19.
Valdes, J., Tarjan, R. E., & Lawler, E. L. (1979). The recognition of series parallel digraphs. Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, 1–12.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2023 Ema Sri Rezeki, Saib Suwilo, Mardiningsih

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.