EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 2, 2024, 725-735 ISSN 1307-5543 – ejpam.com Published by New York Business Global Legal Hop Independent Sequences in Graphs Javier A. Hassan1,∗, Mercedita A. Langamin1, Amy A. Laja1, Bayah J. Amiruddin-Rajik1, Eman C. Ahmad2, Jahiri U. Manditong1 1 Mathematics and Sciences Department, College of Arts and Sciences, MSU Tawi-Tawi College of Technology and Oceanography, Bongao, Tawi-Tawi, Philippines 1 Department of Mathematics and Statistics, College of Science and Mathematics, Western Mindanao State University, Zamboanga City, Philippines Abstract. Let G be any graph. A sequence L = (w1, . . . , wk) of distinct vertices of G is called a legal hop independent sequence if k = 1 or L is a hop independent and NG[wi] \ ⋃i−1 j=1 NG[wj ] ̸= ∅ for every i ∈ {2, · · · , k}. The maximum length of a legal hop independent sequence in G, denoted by αℓh(G), is called the legal hop independence number of G. In this paper, we investigate its relationships with the hop independence and grundy domination parameter of a graph, respectively. In fact, the legal hop independence parameter is at most equal to the grundy domination (resp. hop independence) parameter on any graph G. Moreover, we derive some formulas and bounds of this parameter on some families of graphs, join, and corona of two graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: legal sequence, hop independent set, legal hop independent sequence, legal hop independence number 1. Introduction Independent sets are used to model relationships in networks, such as social networks, computer networks, and biological networks. For example, in a social network, an in- dependent set could represent a group of individuals who are not directly connected or acquainted with each other. Independent sets in graphs had studied on different kinds of graphs (see [2, 11, 17, 18]). In 2022, hop independent set in a graph and its parameter was introduced by J. Hassan et al. [8]. They defined a set S ⊆ V (G) is a hop independet set of G if any two distinct vertices in S are not at a distance two from each other, that is, dG(u,w) ̸= 2 for any distinct vertices u,w ∈ S. The maximum cardinality of a hop independent set of G, ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i2.5061 Email addresses: javierhassan@msutawi-tawi.edu.ph (J. Hassan) merceditalangamin@msutawi-tawi.edu.ph (M. Langamin) amylaja@msutawi-tawi.edu.ph (A. Laja) bayahamiruddin@msutawi-tawi.edu.ph (B. Amiruddin) ahmad.eman@wmsu.edu.ph (E. Ahmad) jahirimanditong@msutawi-tawi.edu.ph (J. Manditong) https://www.ejpam.com 725 © 2024 EJPAM All rights reserved. J. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 725-735 726 denoted by αh(G), is called the hop independence number of G. They have shown that any maximum hop independent set S of G is always a hop dominating, that is, the hop indpendence number of a graph is always greater than or equal to the hop domination parameter. Moreover, they derived some bounds and formulas for some special graphs and graphs under some binary operations. Some studies related to hop independent sets, its variations, and other hop-related concepts can be found in [3, 9, 10, 13, 14]. Recently, J. Hassan and S. Canoy [5], introduced another variant of hop independence in a graph called hop independent hop domination. They have shown that the hop inde- pendent hop domination number of a graph G lies between the hop domination number and the hop independence number of graph G. They have characterized hop independent hop dominating sets in the shadow graph, join, corona, and lexicographic product of two graphs. Moreover, they have obtained exact values or bounds of the hop independent hop domination numbers of these graphs. Furthermore, researchers had studied variants of hop independent hop domination and other related studies on different types of graphs (see [1, 4, 6, 7, 12, 15, 16]). In this paper, new variant of hop independence called legal hop independent sequences in a graph is introduced and investigated. The main focus of this concept is on the sequence of vertices of a graph wherein it must satisfy a certain condition aside from being a hop independent. The authors believe that this study may provide interesting results that would positively contribute to the independence theory and could lead to another interesting studies and application of the parameter. 2. Terminology and Notation Let G = (V (G), E(G)) be a simple and undirected graph. The distance dG(u, v) in G of two vertices u, v is the length of a shortest u-v path in G. The greatest distance between any two vertices in G, denoted by diam(G), is called the diameter of G. A subset D of V (G) is called a dominating of G if for every x ∈ V (G) \ D, there exists y ∈ D such that xy ∈ E(G). The domination number of G, denoted by γ(G), is the minimum cardinality of a dominating set in G. Let S = (v1, v2, · · · , vk) be a sequence of distinct vertices of a graph G, and let Ŝ = {v1, v2, · · · , vk} be a corresponding set of a sequence S. Then S is called a legal closed neighborhood sequence(legal sequence) if NG[vi]\ ⋃i−1 j=1NG[vj ] ̸= ∅ for every i ∈ {2, · · · , k}. If, in addition, Ŝ is a dominating set of G, then S is called a Grundy dominating sequence. The maximum length of a Grundy dominating sequence in a graph G is called the Grundy domination number of G, and is denoted by γgr(G). Any Grundy dominating sequence with length equal to γgr(G) is called a γgr-sequence of G. Let S1 = (v1, . . . , vn) and S2 = (u1, . . . , um) be two sequences of distinct vertices of G. The concatenation of S1 and S2, denoted by S1 ⊕ S2, is the sequence given by S1 ⊕ S2 = (v1, . . . , vn, u1, . . . , um). A subset S of V (G) is called a hop independent if for every pair of distinct vertices x, y ∈ S, dG(x, y) ̸= 2. The maximum cardinality of a hop independent set in G, denoted J. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 725-735 727 by αh(G), is called the hop independence number of G. Any hop independent set S with cardinality equal to αh(G) is called an αh-set of G. A graph is complete if every pair of distinct vertices are adjacent. A complete graph of order n is denoted by Kn. A set S ⊆ V (G) is called a clique in G if the subgraph ⟨S⟩ induced by S is a complete graph. The maximum size or cardinality of a clique of G, denoted by ω(G), is called the clique number of G. Any clique in G with cardinality ω(G) is called an ω-set in G. The complement of a graph G, denoted by G, is the graph with V (G) = V (G) and E(G) = {uv : u, v ∈ V (G) and uv /∈ E(G)}. Let G and H be any two graphs. The join of G and H, denoted by G+H is the graph with vertex set V (G+H) = V (G) ∪ V (H) and edge set E(G+H) = E(G) ∪ E(H) ∪ {uv : u ∈ V (G), v ∈ V (H)} . The corona G and H, denoted by G ◦ H, the graph obtained by taking one copy of G and |V (G)| copies of H, and then joining the ith vertex of G to every vertex of the ith copy of H. We denote by Hv the copy of H in G ◦H corresponding to the vertex v ∈ G and write v +Hv for ⟨{v}+Hv⟩. 3. Results We begin this section by introducing the concept of a legal hop independence in a graph. Definition 1. Let G be any graph. A sequence L = (w1, . . . , wk) of distinct vertices of G is called a legal hop independent sequence if k = 1 or L is a hop independent and NG[wi] \ ⋃i−1 j=1NG[wj ] ̸= ∅ for every i ∈ {2, · · · , k}. The maximum length of a legal hop independent sequence in G, denoted by αℓh(G), is called the legal hop independence number of G. Any legal hop independent sequence L of G with |L̂| = αlh(G), where L̂ = {w1, . . . , wk}, is called an αlh-sequence or a maximum legal hop independent sequence of G. Moreover, we call L̂ an αlh-set of G. Example 1. Consider the graph G = C4 in Figure 1. Let L = (w1, w2). Then NG[w1] = {w1, w2, w4} and NG[w2] = {w1, w2, w3}. From the equations above, we have NG[w2]\NG[w1] = {w1, w2, w3}\{w1, w2, w4} = {w3} ≠ ∅. It follows that L is a legal sequence in G. Since dG(w1, w2) = 1 ̸= 2, this means that L̂ = {w1, w2} is a hop independent set of G. Thus, L = (w1, w2) is a legal hop independent sequence of G. Moreover, since dG(w1, w3) = 2 and dG(w2, w4) = 2, it follows that L is a maximum legal hop independent sequence of G. Therefore, αℓh(G) = 2. J. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 725-735 728 w1 w2 w3w4 G : Figure 1: Graph G with αlh(G) = 2 Remark 1. Let G be a graph. Then (i) a legal sequence of G may not form a hop independent set of G; (ii) a hop independent set of G may not form a legal sequence of G; (iii) if Ŝ is an αh-set of G and form a legal sequence, then S is an αℓh-sequence of G and αℓh(G) = |Ŝ|; and (iv) if L is a maximum legal sequence of G and L̂ is a hop independent set of G, then L is an αℓh-sequence of G and αℓh(G) = |L̂|. Theorem 1. Let G be any graph. Then (i) αℓh(G) ≤ αh(G); (ii) 1 ≤ αℓh(G) ≤ |V (G)| ; and (iii) αℓh(G) ≤ γgr(G). Proof. (i) Let G be any graph and let L be an αℓh-sequence of G. Then its corre- sponding set L̂ is a hop independent set of G. Since αh(G) is the maximum cardinality of a hop independent set in G, it follows that αh(G) ≥ ∣∣∣L̂∣∣∣ = αℓh(G). (ii) Let G be any graph and let x ∈ V (G). Then (x) is a legal hop independent se- quence of G. Hence, αℓh(G) ≥ 1. Since αh(G) ≤ |V (G)| for any graph G, it follows that αℓh(G) ≤ |V (G)| by (i). Consequently, 1 ≤ αℓh(G) ≤ |V (G)| . (iii) Let G be any graph and let L be an αℓh-sequence of G. Then L is a legal sequence of G. Since any γgr-sequence is a maximum legal sequence, we have αℓh(G) = |L̂| ≤ γgr(G). Theorem 2. αℓh(G) = 1 if and only if G is complete graph. Proof. Let αℓh(G) = 1. Suppose G is non-complete. If G is connected, there exist u,w ∈ V (G) such that dG(u,w) = 2. Let x ∈ NG(u) ∩ NG(w). Then w ∈ NG[x]\NG[u], J. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 725-735 729 and so NG[x]\NG[u] ̸= ∅. Thus, L = (u, x) is a legal sequence of G. Since dG(u, x) = 1, it follows that L = (u, x) is a legal hop independent sequence of G. Therefore, αℓh(G) ≥ 2, which is a contradiction. Now, Suppose that G is disconnected graph. Let G1, ..., Gm, where m ≥ 2 be compo- nents of G. Then αℓh(Gi) ≥ 1 for each i ∈ {1, ...,m}. Thus, αℓh(G) = αℓh(G1) + ...+ αℓh(Gm) ≥ 1 + ...+ 1 ≥ 2 since m ≥ 2. However, this a contradiction to our assumption. Consequently, G must be complete graph. For the converse, suppose that G is complete. Then γgr(G) = 1. Therefore, αℓh(G) = 1 by Theorem 3 (ii) and (iii). Theorem 3. Let G be any graph. Then αℓh(G) = |V (G)| if and only if every component of G is trivial. Proof. Suppose that αℓh(G) = |V (G)| . Then V (G) is the maximum αℓh-set of G. Suppose there is a component K of G which is non-trivial. If K is complete, then αℓh(K) = 1. Thus, αℓh(G) ≤ |V (G)|− |V (K)| ≤ |V (G)|− 1, a contradiction. If K is non- complete, then αh(K) ≤ |V (K)|−1.Hence, αh(G) ≤ |V (G)|−1, and so αℓh(G) ≤ |V (G)|−1 by Theorem 3(i), a contradiction. Therefore, every component of G is trivial. Conversely, suppose that every component of G is trivial. Let V (G) = {v1, v2, ..., vm}. Then ⟨{x1}⟩, ⟨{x2}⟩, ..., ⟨{xm}⟩ are the components of G. Thus, NG[xi] = {xi} for each i ∈ {1, 2, ...,m}, and so xj ∈ NG[xj ]\ j−1⋃ k=1 NG[xk] ∀ j ∈ {2, ...,m}. That is, S = (v1, v2, ..., vm) is a legal sequence of G. Notice that dG(xs, xt) ̸= 2 ∀ s ̸= t, where s, t ∈ {1, 2, ...,m}. Therefore, S is a legal hop independent sequence of G. Consequently, αℓh(G) = |V (G)| . The following result follows from the above Theorem. Corollary 1. Let m ≥ 1 be any positive integer. Then αℓh(Km) = m. Theorem 4. Let s and t be positive integers that satisfy 2 ≤ s ≤ t. Then there exists a connected graph K such that αℓh(K) = s and αh(K) = t. Proof. Supose that s < t. Let q = t − s and consider the graph K in Figure 2, where ⟨{x,ws, u1, u2, ...uq}⟩ and ⟨{y, ws, u1, u2, ...uq}⟩ induced a complete graph, respec- tively. Let L = (w1, w2, ..., ws) and L̂0 = {w1, w2, ..., ws, u1, u2, ..., uq}. Then L and L̂0 are maximum legal hop independent sequence and maximum hop independent set of K, re- spectively. Therefore, αℓh(K) = s and αh(K) = s+q = t, and so αℓh(K) = s < t = αh(K). J. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 725-735 730 . . . w1 . . . w2 w3 ws−1 x u1 ws uq u2 y K : Figure 2: A graph K′ with αlh(K ′) < αh(K ′) For s = t, consider the graph K ′ in Figure 3. Let Q = (a1, a2, ..., at) and Q̂ = {a1, a2, ...at}. Then Q and Q̂ are maximum legal hop independent sequence and maximum hop independent set of K ′, respectively. Thus, αℓh(K ′) = t = s = αh(K ′). a1 . . . K ′ : a2 a3 at−1 at Figure 3: A graph K′ with αlh(K ′) = αh(K ′) Definition 2. Let G be any graph. A sequence L = (a1, . . . , an) is called a clique legal sequence if n = 1 or L is a legal sequence and its corresponding set L̂ induces a complete graph. The maximum length of a clique legal sequence in G, denoted by αcℓh(G), is called the clique legal number of G. Moreover, we call L̂ a clique legal set of G. Definition 3. Let G be any graph. A clique legal sequence L is called a clique legal dominating sequence or a clique Grundy dominating sequence if its corresponding set L̂ is a dominating set of G. The maximum length of a clique Grundy dominating sequence in G, denoted by γcℓgr(G), is called the clique Grundy domination number of G. Moreover, a clique legal sequence L of G is called a clique legal non-dominating sequence if L̂ is not a dominating set of G. J. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 725-735 731 Theorem 5. [8] Let G and H be graphs. Then S is a non-empty hop independent set of G+H if and only if one of the following statements holds: (i) S ∩ V (H) = ∅ and S ∩ V (G) is a clique in G. (ii) S ∩ V (G) = ∅ and S ∩ V (H) is a clique in H. (iii) S ∩ V (G) and S ∩ V (G) are clique in G and H, repectively. Theorem 6. [6] Let G and H be two non-complete graphs. A sequence D of distinct verices of G + H is a Grundy dominating sequence in G + H if and only if one of the following conditions holds: (i) D is a Grundy dominating sequence of G. (ii) D is a Grundy dominating sequence of H. (iii) D = DG ⊕ (w) for some non-dominating legal closed neighborhood sequence DG of G and w ∈ V (H). (iv) D = DH ⊕ (v) for some non-dominating legal closed neighborhood sequence DH of H and v ∈ V (G). Theorem 7. Let H and K be two non-complete graphs. A sequence L of distinct vertices of H +K is a legal hop independent sequence in H +K if and only if one of the following conditions holds: (i) L is a clique legal sequence in H (ii) L is a clique legal sequence in K (iii) L = LH ⊕ (a), where LH is a clique legal non-dominating sequence in H and a ∈ V (K). (iv) L = LK ⊕ (b), where LK is a clique legal non-dominating sequence in K and b ∈ V (H). Proof. Suppose that L is a legal hop independent sequence of H + K. Assume that L̂ ⊆ V (H). Then L̂ is a clique in H by Theorem 5. By Theorem 6, L is a legal sequence in H. Thus, L is a clique legal sequence in H and so (i) holds. Similarly, if L̂ ⊆ V (K), then L is a clique legal sequence in K. That is, (ii) holds. Now, let LH and LK be subsequences of L such that L̂H = L̂ ∩ V (H) and L̂K = L̂ ∩ V (K). Suppose that L̂H ̸= ∅ and L̂K ̸= ∅. Then L = LH ⊕ (a) for some non- dominating legal sequence LH in H and a ∈ V (K) by Theorem 6. By Theorem 5, LH is clique in H. Thus, LH is a clique legal non-dominating sequence in H, and so (iii) holds. Similarly, by Theorem 5 and Theorem 6, (iv) holds. The converse is clear. J. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 725-735 732 Corollary 2. Let H and K be two non-complete graphs. Then αℓh(H +K) =  max{γcℓgr(H), γcℓgr(K)}, if both H and K admit a clique grundy domination. max{αcℓh(H) + 1, αclh(K) + 1}, if both H and K does not admit a clique grundy domination. max{αcℓh(H) + 1, γcℓgr(K)}, if K admits a clique grundy domination and H does not. max{αcℓh(K) + 1, γcℓgr(H)}, if H admits a clique grundy domination and K does not. Theorem 8. [6] Let G be a complete graph and let H be a non-complete graph. A sequence D of distinct vertices of G+H is a Grundy dominating sequence in G+H if and only if one of the following condition holds: (i) D = (v) for some v ∈ V (G). (ii) D is a Grundy dominating sequence of H. (iii) D = DH ⊕ (v) for some non-dominating legal neighborhood sequence DH of H and v ∈ V (G). Theorem 9. Let S and T be complete and non-complete graph, respectively. A sequence L′ of distinct vertices of S + T is a legal hop independent sequence if and only if one of the following conditions holds: (i) L′ = (s) for some s ∈ V (S). (ii) L′ is a clique legal sequence of T . (iii) L′ = LT ⊕ (w), where LT is a clique legal non-dominating sequence in T and w ∈ V (S). Proof. Let L′ be a legal hop independent sequence of S + T . Assume that L̂′ ⊆ V (S). Since S is complete, L′ = (s) for some s ∈ V (G). Hence, (i) holds. Suppose that L̂′ ⊆ V (T ). Since L̂′ is hop independent in S + T , L̂′ is clique in T by Theorem 5. By Theorem 7, L′ is legal sequence in T . Thus, L′ is a clique legal sequence in T , and so (ii) holds. Now, assume that L̂′ = L̂S ∪ L̂T , where L̂s = L̂′ ∩ V (S) and L̂T = L̂′ ∩ V (T ). Then L̂′ is a dominating set of S + T . By Theorem 8, L′ = LT ⊕ (w) for some non-dominating legal sequence LT of T and w ∈ V (S). Since L̂′ is a hop independent set in S + T , L̂T J. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 725-735 733 must be clique in T . Hence, (iii) holds. The converse is clear. Corollary 3. Let S and T be complete and non-complete graphs, respectively. Then αℓh(S + T ) = { γcℓgr(T ), if T admits a clique grundy domination. αcℓh(T ) + 1, otherwise. Theorem 10. Let G be a connected graph and H be any graph. Then L is a legal hop independent sequence of G ◦H if L̂ = ⋃ v∈v L̂v, where L̂v is a clique legal set in Hv for each v ∈ V (G). Moreover, αℓh(G ◦H) ≥ αcℓh(H) · |V (G)|. Proof. Let L̂ = ⋃ v∈v L̂v, where L̂v is a clique legal set in Hv for some v ∈ V (G). Then L is a legal sequence of G ◦H. Now, let a, b ∈ L̂. If a, b ∈ L̂v, then dG(a, b) = 1. Thus, L̂ is a hop independent of G ◦H, and so we are done. Suppose that a ∈ Lu and b ∈ Lw for some u,w ∈ V (G). Clearly, dG◦H(a, b) ≥ 3. Since a and b are arbitrary, it follows that L̂ is a hop independent set of G ◦ H. Hence, L̂ is legal hop independent set of G ◦ H. Consequently, αℓh(G ◦H) ≥ αcℓh(H) · |V (G)|. 4. Conclusion The concept of legal hop independence in graphs has been introduced and investigated in this study. The parameter was defined on any simple and undirected graph. Moreover, it was found out that the legal hop independence number of a graph is always less than or equal to either Grundy domination number or hop independence number of a graph. The realization result in Theorem 4 says that the difference between the hop independence number and the legal hop independence number of a graph can be made arbitrarily large. Furthermore, some exact values and bounds of the parameter have been obtained on some special graphs, join and corona of two graphs. Some graphs that were not considered in this study could be an interesting cases to consider for further investigation of this newly defined parameter. In addition, researchers may consider to study the complexity and algorithm of determining the legal hop inde- pendence number of any graph. Acknowledgements The authors would like to thank Mindanao State University-Tawi-Tawi College of Technology and Oceanography for funding this research. REFERENCES 734 References [1] V. Bilar, M.A. Bonsocan, J. Hassan, and S. Dagondon. Vertex cover hop dominating sets in graphs. Eur. J. Pure Appl. Math., 17(1):93–104, 2024. [2] E. Davies, M. Jenssen, W. Perkins, and B. Roberts. independent sets, matchings, and occupancy fractions. J. Lond. Math. Soc., 96:211–220, 2017. [3] J. Hassan, AR. Bakkang, and ASS. Sappari. j2-hop domination in graphs: Properties and connections with other parameters. Eur. J. Pure Appl. Math., 16(4):2118–2131, 2023. [4] J. Hassan and S. Canoy. Connected grundy hop dominating sequences in graphs.,. Eur. J. Pure Appl. Math., 16(2):1212–1227, 2023. [5] J. Hassan and S. Canoy. Hop independent hop domination in graphs.,. Eur. J. Pure Appl. Math., 15(4):1783–1796, 2023. [6] J. Hassan and S. Canoy Jr. Grundy dominating and grundy hop dominating sequences in graphs: Relationships and some structural properties. Eur. J. Pure Appl. Math., 16(2):1154–1166, 2023. [7] J. Hassan and S. Canoy Jr. Grundy total hop dominating sequences in graphs. Eur. J. Pure Appl. Math., 16(4):2597–2612, 2023. [8] J. Hassan, S. Canoy Jr., and A. Aradais. Hop independent sets in graphs. Eur. J. Pure Appl. Math., 15(2):467–477, 2022. [9] J. Hassan, A. Lintasan, and N.H. Mohammad. Some properties and realization prob- lems involving connected outer-hop independent hop domination in graphs. Eur. J. Pure Appl. Math., 16(3):1848–1861, 2023. [10] J. Hassan, A. Tapeing, H. Copel, A.R Bakkang, and S.D. Aming. j2-independence parameters of some graphs.,. Eur. J. Pure Appl. Math., 17(1):124–134, 2024. [11] Liu Jiuqiang. Maximal and maximum independent sets in graphs. Dissertations., 1985. [12] S. Canoy Jr. and J. Hassan. Weakly convex hop dominating sets in graphs. Eur. J. Pure Appl. Math., 15(4):1783–1796, 2022. [13] S. Kaida, K.J. Maharajul, J. Hassan, L. S. Laja, A.B. Lintasan, and A.A. Pablo. Certified hop independence: Properties and connections with other variants of inde- pendence. Eur. J. Pure Appl. Math., 17(1):435–444, 2024. [14] J. Manditong, J. Hassan, LS Laja, AA. Laja, NHM. Mohammad, and SU. Kam- don. Connected outer-hop independent dominating sets in graphs under some binary operations. Eur. J. Pure Appl. Math., 16(3):1817–1829, 2023. REFERENCES 735 [15] J. Manditong, A. Tapeing, J. Hassan, A.R. Bakkang, N.H. Mohammad, and S.U. Kamdon. Some properties of zero forcing hop dominating sets in a graph. Eur. J. Pure Appl. Math., 17(1):324–337, 2024. [16] J. Mohamad and H. Rara. On resolving hop domination in graphs. Eur. J. Pure Appl. Math., 14(1):324–337, 2021. [17] H.S. Wilf. The number of maximal independent sets in a tree. SIAM J. Alg. Disc. Meth., 7:125–130, 1986. [18] J. Zito. The structure and maximum number of maximum independent sets in trees. J. Graph Theory., 15(2):207–221, 1991.