Alpha-Cut Fuzzy Tree Parameters: Width, Length, Depth, Breadth, and Connections to Fuzzy Decision Trees
Keywords:
Fuzzy graph, Alpha-cut, Fuzzy tree-width, Fuzzy tree-length, Fuzzy tree-depth, Fuzzy tree-breadth, Fuzzy decision tree, Tree-decomposition, Graph parametersAbstract
This paper develops an alpha-cut framework for four classical graph parameters on finite undirected fuzzy graphs: tree-width, tree-length, tree-depth, and tree-breadth. Each parameter is evaluated on the crisp graph obtained at a positive membership threshold, and its profile is integrated over [0,1]. We show that these profiles are bounded step functions and obtain exact finite-sum formulas for the integrated parameters. We establish threshold monotonicity for width and depth, crisp reduction, and inequalities connecting the integrated length and breadth parameters. A strengthened width–depth inequality explicitly accounts for the maximum vertex-membership degree. We also examine fuzzy decision trees under a normalized product-routing model. For a graph induced by test-node activations and ancestor relations, we derive exact expressions for integrated width and depth and establish bounds involving soft path length. Compatible feature-interaction hierarchies provide further structural bounds. These findings distinguish alpha-cut aggregation from fuzzy-bag approaches and characterize its relationship to selected decision-tree structures without making claims about predictive performance.
Downloads
References
Zadeh, L. A. (1965). Fuzzy sets. Information and Control, 8(3), 338–353. https://doi.org/10.1016/S0019-9958(65)90241-X
Das, S., & Kar, S. (2013). Intuitionistic multi fuzzy soft set and its application in decision making. In Pattern Recognition and Machine Intelligence: 5th International Conference, PReMI 2013 (pp. 587–592). Springer. https://doi.org/10.1007/978-3-642-45062-4_82
Atanassov, K. T., & Gargov, G. (2017). Intuitionistic fuzzy logics. Springer.
Wang, H., Smarandache, F., Zhang, Y., & Sunderraman, R. (2010). Single valued neutrosophic sets. Infinite Study. https://fs.unm.edu/neut/SingleValuedNeutrosophicSets.pdf
Smarandache, F. (1999). A unifying field in logics: Neutrosophic logic. In Philosophy (pp. 1–141). American Research Press. https://arxiv.org/pdf/math/0101228
Nordo, G., Smarandache, F., et al. (2027). Plithogenic topological spaces. Neutrosophic Sets and Systems, 103, 17–47. https://doi.org/10.5281/zenodo.22821085
Angel, N., Pandiammal, P., & Martin, N. (2026). Plithogenic cognitive maps with extended plithogenic representations & applications. New Trends in Neutrosophic Theories and Applications, Volume V, 126. https://doi.org/10.5281/zenodo.20426406
Rosenfeld, A. (1975). Fuzzy graphs. In Fuzzy sets and their applications to cognitive and decision processes (pp. 77–95). Elsevier.
Al-Hawary, T. (2011). Complete fuzzy graphs. International Journal of Mathematical Combinatorics, 4, 26.
Mordeson, J. N., & Nair, P. S. (2012). Fuzzy graphs and fuzzy hypergraphs (Vol. 46). Physica. https://doi.org/10.1007/978-3-7908-1854-3
Broumi, S., Bakali, A., Talea, M., Smarandache, F., & Verma, R. (2022). Computing minimum spanning tree in interval valued bipolar neutrosophic environment. Collected Papers. Volume VII: On Neutrosophic Theory and Applications, 7(5), 143.
Broumi, S., Bakali, A., & Bahnasse, A. (2018). Neutrosophic sets: An overview. Infinite Study. https://www.researchgate.net/publication/328019074_Neutrosophic_Sets_An_Overview
Broumi, S., Talea, M., Bakali, A., & Smarandache, F. (2016a). Interval valued neutrosophic graphs. Critical Review, XII, 2016, 5–33.
Broumi, S., Talea, M., Bakali, A., Smarandache, F., & Kumar, P. K. (2017). Shortest path problem on single valued neutrosophic graphs. In 2017 International Symposium on Networks, Computers and Communications (ISNCC) (pp. 1–6). IEEE. https://doi.org/10.1109/ISNCC.2017.8071993
Zhao, Z., & Zhang, X. (2026). FRF-FHG: Constructing fuzzy hypergraphs based on FRF. Journal of Intelligence and Knowledge Engineering, 4(1), 209. https://doi.org/10.62517/jike.202604130
Datta, R., Baitalik, S., Das Choudhury, S., Chattopadhyay, A. K., & Das, A. K. (2026). Fuzzy hypergraph feature association map for high-dimensional feature selection in agriculture and remote sensing. International Journal of Fuzzy Systems, 1–14. https://doi.org/10.1007/s40815-026-02267-2
Fujita, T. (2026). Tripolar fuzzy hypergraph and tripolar fuzzy superhypergraph. Journal of Mathematics and Informatics, 31, 5–18. https://doi.org/10.22457/jmi.v31a02275
Robertson, N., & Seymour, P. D. (1984). Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1), 49–64. https://doi.org/10.1016/0095-8956(84)90013-3
Bodlaender, H. L. (1997). Treewidth: Algorithmic techniques and results. In International Symposium on Mathematical Foundations of Computer Science (pp. 19–36). Springer. https://doi.org/10.1007/BFb0029946
Bodlaender, H. L., Grigoriev, A., & Koster, A. M. (2005). Treewidth lower bounds with brambles. In Algorithms–ESA 2005: 13th Annual European Symposium (pp. 391–402). Springer.
Robertson, N., & Seymour, P. D. (1983). Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B, 35(1), 39–61. https://doi.org/10.1016/0095-8956(83)90079-5
Kaplan, H., & Shamir, R. (1996). Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM Journal on Computing, 25(3), 540–561. https://doi.org/10.1137/S0097539793258143
Dourisboure, Y., Dragan, F. F., Gavoille, C., & Yan, C. (2007). Spanners for bounded tree-length graphs. Theoretical Computer Science, 383(1), 34–44. https://doi.org/10.1016/j.tcs.2007.03.058
Leitert, A., & Dragan, F. F. (2016). On strong tree-breadth. In International Conference on Combinatorial Optimization and Applications (pp. 62–76). Springer. https://doi.org/10.1007/978-3-319-48749-6_5
Nešetřil, J., & De Mendez, P. O. (2006). Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 27(6), 1022–1041. https://doi.org/10.1016/j.ejc.2005.01.010
Gottlob, G., Leone, N., & Scarcello, F. (1999). Hypertree decompositions and tractable queries. In Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (pp. 21–32).
Gottlob, G., Leone, N., & Scarcello, F. (2001). Hypertree decompositions: A survey. In Mathematical Foundations of Computer Science 2001: 26th International Symposium, MFCS 2001 (pp. 37–57). Springer. https://doi.org/10.1007/3-540-44683-4_5
Robertson, N., & Seymour, P. D. (1991). Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2), 153–190. https://doi.org/10.1016/0095-8956(91)90061-N
Oum, S.-i. (2008). Rank-width is less than or equal to branch-width. Journal of Graph Theory, 57(3), 239–244. https://doi.org/10.1002/jgt.20280
Munaro, A., & Yang, S. (2023). On algorithmic applications of sim-width and mim-width of (H1, H2)-free graphs. Theoretical Computer Science, 955, 113825. https://doi.org/10.1016/j.tcs.2023.113825
Fujita, T., & Smarandache, F. (2026). Fuzzy, neutrosophic, and uncertain graph theory: Properties and applications. Infinite Study.
Fujita, T., Batiha, I. M., Gulistan, M., Batiha, B., Al Smadi, E. L., & Jebril, I. (2026). Tree decompositions in fuzzy graphs: Foundations and structural insights. Statistics, Optimization & Information Computing, 16(1), 312–326. https://doi.org/10.19139/soic-2310-5070-3117
Kotsiantis, S. B. (2013). Decision trees: A recent overview. Artificial Intelligence Review, 39, 261–283. https://doi.org/10.1007/s10462-011-9272-4
Murthy, S. K. (1998). Automatic construction of decision trees from data: A multi-disciplinary survey. Data Mining and Knowledge Discovery, 2(4), 345–389. https://doi.org/10.1023/A:1009744630224
Olaru, C., & Wehenkel, L. (2003). A complete fuzzy decision tree technique. Fuzzy Sets and Systems, 138(2), 221–254. https://doi.org/10.1016/S0165-0114(03)00089-7
Janikow, C. Z. (1998). Fuzzy decision trees: Issues and methods. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 28(1), 1–14. https://doi.org/10.1109/3477.658573
Pang, B. (2025). Neutrosophic information gain for decision tree construction: Application to teaching performance of tennis instructors in sports universities. Neutrosophic Sets and Systems, 91(1), 9. https://digitalrepository.unm.edu/cgi/viewcontent.cgi?article=3715&context=nss_journal
Olgun, N., & Hatip, A. (2020). The effect of the neutrosophic logic on the decision tree. Quadruple Neutrosophic Theory and Applications, 17, 238–253.
Kloks, T. (1994). Treewidth: Computations and approximations. Springer. https://doi.org/10.1007/BFb0045375
Bonnet, É. (2024). Treewidth inapproximability and tight ETH lower bound. arXiv preprint arXiv:2406.11628.
Gottlob, G., Greco, G., Scarcello, F., et al. (2014). Treewidth and hypertree width. In Tractability: Practical Approaches to Hard Problems (Vol. 1, p. 20).
Broumi, S., Talea, M., Bakali, A., & Smarandache, F. (2016b). Single valued neutrosophic graphs. Journal of New Theory, 10, 86–101. https://doi.org/10.5281/zenodo.50940
Smarandache, F. (2020). Extension of hypergraph to n-superhypergraph and to plithogenic n-superhypergraph, and extension of hyperalgebra to n-ary (classical-/neutro-/anti-) hyperalgebra. Infinite Study. https://fs.unm.edu/nss8/index.php/111/article/view/198
Bretto, A. (2013). Hypergraph theory: An introduction. Springer. https://doi.org/10.1007/978-3-319-00080-0
Feng, Y., You, H., Zhang, Z., Ji, R., & Gao, Y. (2019). Hypergraph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence. https://arxiv.org/abs/1809.09401
Ghods, M., Rostami, Z., & Smarandache, F. (2022). Introduction to neutrosophic restricted superhypergraphs and neutrosophic restricted superhypertrees and several of their properties. Neutrosophic Sets and Systems, 50, 480–487. https://digitalrepository.unm.edu/nss_journal/vol50/iss1/28/
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Takaaki Fujita, Ajoy Kanti Das (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
