**
Gajendra Pratap Singh **
School of Computational and Integrative Sciences, Jawaharlal Nehru University, New Delhi-110067, India.

**
Sujit Kumar Singh **
School of Computational and Integrative Sciences, Jawaharlal Nehru University, New Delhi-110067, India.

**
Madhuri Jha **
School of Computational and Integrative Sciences, Jawaharlal Nehru University, New Delhi-110067, India.

DOI https://doi.org/10.33889/IJMEMS.2020.5.1.008

**Abstract**

Boolean Petri net (BPN) and Crisp Boolean Petri net (CBPN) is a well-studied graph model since 2010 which has several applications in mathematical modeling of complex or tricky networks. Modeling any network with Petri net which can generate binary numbers as marking vectors in its reachability tree is still has much uses. In CBPN with a minimum number of transition and minimum number of steps of reachability tree, minimal execution time to run the machine has not been noted till date, thus it’s necessary to sort out this problem. Possibly it may occur due to some forbidden structure which hinders any 1-safe Petri net to be a CBPN. In this paper, we present some forbidden digraphs whose presence interrupts the generation of binary n-vectors exactly once. Any 1-safe Petri net is not a CBPN if it contains any of the subnet induced to the four forbidden structures discussed in this paper.

**Keywords-** Petri net, Binary vectors, Boolean Petri net, Crisp Boolean Petri net, Forbidden graphs.

**Citation**

Singh, G. P., Singh, S. K., & Jha, M. (2020). Existence of Forbidden Digraphs for Crisp Boolean Petri Nets. *International Journal of Mathematical, Engineering and Management Sciences*, *5*(1), 83-95. https://doi.org/10.33889/IJMEMS.2020.5.1.008.

**Conflict of Interest**

All the authors have no conflict of interest.

**Acknowledgements**

The first author is thankful to the Department of Science and Technology (SERB) (PID: ECR/2017/003480) and UPOE-II (ID-257) and DST purse grant for providing research facility. The authors are expressing their deep gratitude to anonymous reviewers, editors for their valuable suggestions and comments.

**References**

Francis, M., Hell, P., & Stacho, J. (2015, January). Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1708-1727). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.

Greenwell, D.L., & Hemminger, R.L. (1972). Forbidden subgraphs for graphs with planar line graphs. Discrete Mathematics, 2(1), 31-34.

Gupta, S., Kumawat, S., & Singh, G.P. (2019a, July). Fuzzy Petri net representation of fuzzy production propositions of a rule based system. In International Conference on Advances in Computing and Data Sciences (pp. 197-210). Springer, Singapore.

Gupta, S., Singh, G.P., & Kumawat, S. (2019b). Petri net recommender system to model metabolic pathway of polyhydroxyalkanoates. International Journal of Knowledge and Systems Science, 10(2), 42-59.

Harary, F. (2015). A seminar on graph theory. Courier Dover Publications.

Hogben, L., & Van Der Holst, H. (2007). Forbidden minors for the class of graphs G with ξ (G)⩽ 2. Linear Algebra and its Applications, 423(1), 42-52.

Jensen, K. (1993, June). An introduction to the theoretical aspects of coloured Petri nets. In Workshop/School/Symposium of the REX Project (Research and Education in Concurrent Systems) (vol. 803, pp. 230-272). Springer, Berlin, Heidelberg.

Jensen, K., & Rozenberg, G. (2012). High-level Petri nets: theory and application. Springer Science & Business Media.

Kansal, S., Acharya, M., & Singh, G.P. (2011b). Uniqueness of minimal 1-safe Petri net generating all the binary n-vectors as its marking vectors exactly once. Scientiae Mathematicae Japonicae, 74(2 & 3), 117-120.

Kansal, S., Acharya, M., & Singh, G.P. (2012). Boolean Petri nets. In Petri Nets-Manufacturing and Computer Science, IntechOpen, 381-406.

Kansal, S., Singh, G.P., & Acharya, M. (2010). On petri nets generating all the binary n-vectors. Scientiae Mathematicae Japonicae, 71(2), 209-216.

Kansal, S., Singh, G.P., & Acharya, M. (2011a). 1-Safe Petri nets generating every binary n-vector exactly once. Scientiae Mathematicae Japonicae, 74(1), 29-36.

Kansal, S., Singh, G.P., & Acharya, M. (2015). On the problem of characterizing boolean Petri nets. International Journal of Computer Applications, 128(2), 0975, 8887.

Kumar, R., Singh, G.P., Pandey, S.K., & Shekhawat, V.J. (2018). Non-cyclic hydrocarbons: generating all the binary n-vectors, special issue on Mathematical Sciences (graph theory), Vigyan Garima Sindu, Commission for Scientific and Technical Terminology, Ministry of Human Resource Development, Govt. of India, ISSN: 2320-7736, 105, 24-28 (in hindi version).

Lekkeikerker, C., & Boland, J. (1962). Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 51(1), 45-64.

Mayr, E.W. (1984). An algorithm for the general Petri net reachability problem. SIAM Journal on Computing, 13(3), 441-460.

Murata, T. (1989). Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4), 541-580.

Panda, B.S. (1999). The forbidden subgraph characterization of directed vertex graphs. Discrete Mathematics, 196(1-3), 239-256.

Pastor, E., Roig, O., Cortadella, J., & Badia, R.M. (1994, May). Petri net analysis using boolean manipulation. In International Conference on Application and Theory of Petri Nets (pp. 416-435). Springer, Berlin, Heidelberg.

Petri, C.A., & Reisig, W. (2008). Petri net. Scholarpedia, 3(4), 6477.

Piestrak, S.J. (1995). A high-speed realization of a residue to binary number system converter. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 42(10), 661-663.

Rosen, K.H., & Krithivasan, K. (2012). Discrete mathematics and its applications: with combinatorics and graph theory. Tata McGraw-Hill Education, India.

Singh, G.P., & Gupta, A. (2019, March). A Petri net analysis to study the effects of diabetes on cardiovascular diseases, IEEE Xplore, ISBN: 978-93-80544-36-6 (accepted).

Singh, G.P., & Singh, S.K. (2019). Petri net recommender system for generating of perfect binary tree. International Journal of Knowledge and Systems Science, 10(2), 1-12.

Szwarcfiter, J.L., & Cerioli, M.R. (1999). Characterizing intersection graphs of substars of a star by forbidden subgraphs. Relatório Técnico NCE, 33(99), 1-11.

Tondato, S.B., Gutierrez, M., & Szwarcfiter, J.L. (2005). A forbidden subgraph characterization of path graphs. Electronic Notes in Discrete Mathematics, 19, 281-287.