Approachable‎ ‎ graph (tree) and ‎Its ‎application ‎in hyper (network)

Document Type : Research Paper


Department of Mathematics, University of Payame Noor, P.O.Box 19395-4697, Tehran, Iran.


A hypertree is a special type of connected hypergraph that removes‎ ‎any‎, ‎its hyperedge then results in a disconnected hypergraph‎. ‎Relation between hypertrees (hypergraphs) and trees (graphs) can be helpful to solve real problems in hypernetworks and networks and it is the main tool in this regard‎. ‎The purpose of this paper is to introduce a positive relation (as $\alpha$-relation) on hypertrees that makes a connection between hypertrees and trees‎. ‎This relation is dependent on some parameters such as path‎, ‎length of a path‎, ‎and the intersection of hyperedges‎. ‎For any $q\in \mathbb{N}‎, ‎$ we introduce the concepts of a derivable tree‎, ‎$(\alpha‎, ‎q)$-hypergraph‎, ‎and fundamental $(\alpha‎, ‎q)$-hypertree for the first time in this study and analyze the structures of derivable trees from hypertrees via given positive relation‎. ‎In the final‎, ‎we apply the notions of derivable trees‎, ‎$(\alpha‎, ‎q)$-trees in real optimization problems by modeling hypernetworks and networks based on hypertrees and trees‎, ‎respectively.‎‎‎


Main Subjects

[1] M. A. Bahmanian and M. Newman, Extending Factorizations of Complete Uniform Hypergraphs, J. Comb., 38 (2018) 1309–1335.
[2] R. Aharoni, R. Holzman and Z. Jiang, Rainbow Fractional Matchings, J. Comb., 39 (2019) 1191–1202.
[3] C. Berge, Graphs and Hypergraphs, North Holland, 1979.
[4] M. Balko, D. Gerbner, D. Y. Kang, Y. Kim and C. Palmer, Hypergraph Based Berge Hypergraphs, Graphs Comb., 38 (2022) 1–13.
[5] A. Boussairi, B. Chergui, P. Ille and M. Zaidi, Prime 3-Uniform Hypergraphs, Graphs Comb., 37 (2021) 2737–2760.
[6] A. Dahari and N. Linial, In Search of Hyperpaths, Discrete. Comput. Geom., 69 (2023) 399–421.
[7] H. Guo and B. Zhou, On the spectral radius of uniform hypertrees, Linear. Algebra. Appl., 558 (2018) 236–249.
[8] M. Hamidi and R. Ameri, α-Derivable digraphs and its application in wireless sensor networking, Discrete Math. Algorithms Appl., 12 (2020) 22 pp.
[9] M. Hamidi and A. Borumand Saeid, Creating and Computing Graphs from Hypergraphs, Kragujev. J. Math., 43 (2019) 139–164.
[10] M. A. Henning and A. Yeo, Affine Planes and Transversals in 3-Uniform Linear Hypergraphs, Graphs Comb., 37 (2021) 867–890.
[11] M. Hamidi, A. Borumand Saeid, On Derivable Tree, Trans. Comb., 8 no. 2 (2019) 21–43.
[12] M. Kahle and A. Newman, Topology and Geometry of Random 2−Dimensional Hypertrees, Discrete. Comput. Geom., 67 (2022) 1229–1244.
[13] R. S. Rajan, K. J. Kumar, A. A. Shantrinal, T. M. Rajalaxmi, I. Rajasingh and K. Balasubramanian, Biochemical and phylogenetic networks-I: hypertrees and corona products, J. Math. Chem., 59 (2021) 676–698.
[14] G. H. Shirdel and B. Vaez-Zadeh, Finding a minimal spanning hypertree of a weighted hypergraph, J. Comb. Optim., 44 (2022) 894–904.
[15] M. D. Staic and S. R. Lippold, Partitions of the complete hypergraph K63 and a determinant-like function, J. Algebraic Comb., 56 (2022) 969–1003.
Volume 13, Issue 3 - Serial Number 3
September 2024
Pages 287-304
  • Receive Date: 25 October 2022
  • Revise Date: 16 June 2023
  • Accept Date: 01 October 2023
  • Published Online: 01 September 2024