Authors: Stevanović, Dragan 
Title: On the number of maximal independent sets of vertices in star-like ladders
Journal: Fibonacci Quarterly
Volume: 39
Issue: 3
First page: 211
Last page: 220
Issue Date: 1-Jun-2001
Rank: M23
ISSN: 0015-0517
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
Publisher: Fibonacci Association

Show full item record


checked on Jun 16, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.