Quick search
Go!

INDEPENDENCE POLYNOMIALS OF SOME GRAPHS WITH EXTREMAL FIBONACCI INDEX


EUGEN MANDRESCU 1, ION MIRICA 2
1. Department of Computer Science, Holon Institute of Technology, Israel, email: eugen_m@hit.ac.il
2. Department of Mathematics and Informatics, Faculty of Sciences, University "Dunarea de Jos" Galati, Romania, email: ion.mirica@ugal.ro

Issue:

SSRSMI, Number 1, Volume XXI

Section:

Volume 21, Number 1

Abstract:

An independent set in a graph G is a set of pairwise non-adjacent

vertices, and the independence number α(G) is the cardinality of a maximum stable set in G. The independence polynomial of G is

I(G;x)=s0+s1x+s2x2+...+sαxα, α=α(G),

where sk is the number of independent sets of size k in G (I. Gutman and F. Harary, 1983). The Fibonacci index Fib(G) of a graph G is the number of all its independent sets, i.e., Fib(G)=I( G;1). Tight lower and upper bounds for Fibonacci index are known for general graphs, connected or not, and the corresponding extremal graphs are characterized [6], [15].

In this paper, we give explicit formulae for independence polynomials of these extremal graphs, which we further use to analyze some of their properties (unimodality, log-concavity).

Keywords:

[n/a]

Code [ID]:

SSRSMI201101V21S01A0011 [0003413]

Full paper:

Download pdf


Copyright (c) 1995-2007 University of Bacău