On the number of maximal independent sets of vertices in star-like ladders

Abstract

Let MIS stand for the maximal independent set of vertices. Denote the number of MIS of G by MG. Sanders [1] exhibits a tree p(P„), called an extended path, formed by appending a single degree-one vertex to each vertex of a path on n vertices, and proves Mp^P) = Fn+2 • In this paper we Introduce a new class of graphs, called star-like ladders, and show that the number of MIS In star-like ladders has a connection to the Fibonacci numbers. In particular, we show that ML = 2Fp+h where Lp Is the ladder with/? squares. Remember that the ladder Lp, p>\9 Is the graph with 2p + 2 vertices {%¥,-1/ = 0,1,...,p) and edges {utuM, vtvi+l \ i = 0,1,..., p -1} u {u^ | / = 0,1,..., /?}. Two end edges of the ladder Lp are the edges joining vertices of degree 2. The graph obtained by identifying an end edge of ladder Lp with an edge e of a graph G Is denoted by G[e, p]. For the sake of completeness, we will put G[e, 0] = G. If pi,..., pk e N and el9...9ek are the edges of G, then we will write G[(el9...,ek),(#,...,pk)]forG[ex,pj...[ek,pk]. The star-like ladder SL(pl9...,pk)is the graph K2[(e, ...,e),(pl,...,pky],where e Is the edge of K2. We have that Lp = SL(p) = K2 [e, p], p e N