pith. sign in

arxiv: 1105.1940 · v1 · pith:IWH6NPBLnew · submitted 2011-05-10 · 🧮 math.CO

Independent sets in chain cacti

classification 🧮 math.CO
keywords cactichainindependentnumbersetsmeta-chainsorto-chainsrecurrence
0
0 comments X
read the original abstract

In this paper chain cacti are considered. First, for two specific classes of chain cacti (orto-chains and meta-chains of cycles with h vertices) the recurrence relation for independence polynomial is derived. That recurrence relation is then used in deriving explicit expressions for independence number and number of maximum independent sets for such chains. Also, the recurrence relation for total number of independent sets for such graphs is derived. Finaly, the proof is provided that orto-chains and meta-chains are the only extremal chain cacti with respect to total number of independent sets (orto-chains minimal and meta-chains maximal).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.