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 |

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 |

Publisher: | Fibonacci Association |

Show full item record

#### SCOPUS^{TM}

Citations

1
checked on Jun 16, 2024

#### Page view(s)

33
checked on May 9, 2024

#### Google Scholar^{TM}

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