Accepted February 10, 2012) Keywords: Independence polynomial

ON THE INDEPENDENCE POLYNOMIALS OF CERTAIN MOLECULAR GRAPHS

MOHAMMAD H. REYHANI, SAEID ALIKHANI^a, ROSLAN HASNI^b*

Department of Mathematics, Faculty of Science, Islamic Azad University, Yazd Branch, Yazd, Iran

aDepartment of Mathematics, Yazd University 89195-741, Yazd, Iran

bSchool of Mathematical Sciences, Universiti Sains Malaysia 11800 USM, Penang, Malaysia

The independence polynomial of a molecular graph G is the polynomial k

x

k

i x G

I ^{( , ) =} 

^{, where ik} denote the number of independent sets of cardinality k in G. In this paper, we consider specific graphs denoted by G(m) and G₁(m)G₂ and obtain formulas for their independence polynomials which are in terms of Jacobsthal polynomial. Also we compute the independece polynomal of another kind of graphs.

(Recieved November 17, 2011; Accepted February 10, 2012)

Keywords: Independence polynomial; Jacobsthal polynomial; Graph

1. Introduction

A simple graph

G = ( V , E )

is a finite nonempty set V(G) of objects called vertices together with a (possibly empty) set E(G) of unordered pairs of distinct vertices of G called edges. In chemical graphs, the vertices of the graph correspond to the atoms of the molecule, and the edges represent the chemical bonds.

An independent set of a graph G is a set of vertices where no two vertices are adjacent. The independence number is the size of a maximum independent set in the graph. For a graph G with independence



, let i_kdenote the number of independent sets of cardinality k in

G (

k = 0,1,



, 

). The independence polynomial of G,

( , ) = ,

0

= k k k

i x x

G

I 

^ is the generating

polynomial for the independent sequence

( i

₀

, i

₁

, i

₂

,



, i

_

)

([3]). The path P₄ on 4 vertices, for example, has one independent set of cardinality 0 (the empty set), four independent sets of cardinality 1, and three independent sets of cardinality 2; its independence polynomial is then

4, )=1 4 3 2

(P x x x

I   .

Hoede and Li [5] obtained the following recursive formula for the independence polynomial of a graph.

Theorem 1 . For any vertex v of a graph G, I(G,x)=I(Gv,x)xI(G[v],x) where

[v ]

is the closed neighberhood of v , contains of v , together with all vertices incident with

v .

       

*Corresponding author: [email protected]

Let us observe that if G and H are isomorphic, then I(G,x)=I(H,x). The converse is not generally true. For Two graphs G and H are independent equivalent, written G ~ H, if

) , (

= ) ,

(G x I H x

I . A graph G is independent unique, if I(H,x)=I(G,x) implies that H G. Let

[G ]

denote the independent equivalence class determined by the graph G under the equivalence relation~. Clearly, G is independent unique if and only if

[ G ] =

{G}. A zero of

) , (G x

I is called a independence zero of G.

The corona of two graphs G₁ and G₂, as defined by Frucht and Harary in [4], is the graph G₁G₂formed from one copy of G_{1 and} |V(G₁)|copies of G₂, where the ith vertex of G1 is adjacent to every vertex in the ith copy of G₂. The corona GK₁, in particular, is the graph constructed from a copy of G, where for each vertex

v  V

(G), a new vertex v and a pendant edge vv' are added.

In Section 2, we study Jacobsthal polynomial and introduce two graphs with specific structures denoted by G(m) and

G

₁

( m ) G

₂. Using the results related to Jacobsthal polynomial, we compute the independence polynomials of G(m) and

G

₁

( m ) G

₂ in Section 3.

2. Jacobsthal polynomial

Jacobsthal polynomials,

J

_n

(x )

, named after the German mathematician E. Jacobsthal are related to Fibonacci polynomials. They are defined by

) ( )

(

= )

( x J

₁

x xJ

₂

x J

_{n n}



_n

where

J

₁

( x ) = J

₂

( x ) = 1

(see [6], p.469).

In this section, we shall find the zeros of

J

_n

(x )

. First, we need the following two lemmas to obtain a solution of Jacobsthal polynomials.

Lemma 1 . For any real number u,

( ) = (1 ) ( )

¹

.

1 0

=

2 n i n i

i

n

u u u u

J

^{ }



 

 

Proof. It is clear that the result holds when n=2. Now let n3. By induction, we have

)

( ) ( ) (

= )

( u

²

u J

₁

u

²

u u

²

u J

₂

u

²

u

J

_n



_n

  

_n



i n n i

i i

n n i

i

u u u

u u

u

^{ }

 

 











 



^{3 3}

0

= 2

2 2 0

=

) ( ) (1 ) ( )

( ) (1

=

i n n i

i i n n i

i

u u

u

u

^{  }

 

 









 



^{3 1 2}

0

= 2 2

0

=

) ( ) (1 )

( ) (1

=

i n n i

i

i n n i

i n

u u

u u u





 



 





















2 3 1

0

=

3 2 0

= 2

) ( ) (1

) ( ) (1 )

(1

=

i n n i

i

n

u u

u

^{ }







 

 

^{3 1}

0

=

2

(1 ) ( ) )

(1

=

. ) ( ) (1

=

¹

1 0

=

i n n i

i

u

u

^{ }



 



^▄

Corollary 1 . For any real number u ,

(2 u  1) J

_n

( u

²

 u ) = (1  u )

ⁿ

 (  u )

ⁿ

.

Proof. The result follows from Lemma 1 by using the identity

,

) (

=

¹

1 0

=

 





 



 



ⁿ



^{ i n i}

i n

n

b a b a b

a

for

a = 1  u

, b=u. ▄

Lemma 2 . ( [2], p.64) For real numbers a, b and positive integer n ,

















 



  







 



  













. 2 ;

2 )

)(

(

, 2 ;

2 )

(

=

2 2 2

2

1

= 2 2 2

1

1

=

even is n n

ab s b a b a b a

odd is n n

ab s b a b a b

a n

s n

n s n





cos cos

Theorem 2 . For any positive integer n ,

2 .

2 1 2

= ) (

2 1

1

=

 

 



  







n x s x

x J

n

s n

cos



Proof. If put

a = 1  u

, b=u, we have

a  b = a

²

 b

²

= 1  2 u

, therefore by using Lemma 2 and Corollary 1, for any real number

2

 1

 u

,

2 . ) 2(

1 2 2

= )

(

^{2 2}

2 1

1

=

2





 



    

 

 



n u s

u u

u u

u J

n

s n

cos



Observe that for any real number x with

4

>  1

x

, there is a real number

2

 1



u

such that

x u

u

²

 =

. Thus for each real number with

4

>  1

x

,

2 .

2 1 2

= ) (

2 1

1

=

 

 



  



 



n x s x

x J

n

s n

cos



Since J_n(x) is a polynomial with degree less than n, the above equality also holds for any real number

4

 1



x

. Thus the result is obtained. ▄

3. Independence polynomial of certain graphs

In this section we consider some specific graphs and compute their independence polynomial (see [1]). Let P_m1 be a path with vertices labeled by y₀,y₁,,y_m^{, for}

m  0

and let G be any graph. Denote by

( )

0

m

G

_v (or simply G(m), if there is no likelihood of confusion) a graph obtained from G by identifying the vertex

v

₀ of G with an end vertex

y

₀ of P_m1 (see Figure 1). For example, if G is a path P₂, then G(m)=P₂(m) is the path P_m2. Also, we denote the graph obtained from graphs G₁ and G₂ by adding a path P_m from a vertex in G₁ to a vertex

of G₂, by G₁(m)G₂. (Figure 1).

Fig.1. Graphs G(m) and G₁(m)G₂, respectively.

Theorem 3 . Let n2 be integer. Then, the independence polynomial of G(n) is

).

, ( ) ( )

(1), ( ) (

= ) ), (

( G n x J x I G x xJ

₁

x I G x

I

_n



_n

Proof. Proof by induction on n. Since

J

₁

( x ) = J

₂

( x ) = 1

, the result is true for

n = 2

by Theorem 1. Now suppose that the result is true for all natural numbers less than n and prove it for n. By using Theorem 1 for

v = y

_n, and induction hypothesis, we have

= ) 2), ( ( ) 1), ( (

= ) ), (

(G n x I G n x xI G n x

I   

) , ( ) ( )

(1), ( ) (

= J

_n1

x I G x  xJ

_n2

x I G x ) , ( ) ( )

(1), ( ) (

( J

₂

x I G x xJ

₃

x I G x

x

_n



_n



) , ( )) ( )

( ( ) (1), ( )) ( )

( (

= J

_n1

x  xJ

_n2

x I G x  x J

_n2

x  xJ

_n3

x I G x ).

, ( ) ( )

(1), ( ) (

= J

_n

x I G x  xJ

_n1

x I G x

_▄

The following theorem gives the formula for computing the independence polynomial of graphs 2

1

( m ) G

G

as shown in Figure 1 :

Theorem 4 . Let n5 be integer. The independence polynomial of

G

₁

( n ) G

₂ is

)

, ( ) (1), ( ( ) ( ) (1), ( ) (1), (

= ) , ) ( (

2 1

2 2

1 2 1

x G I x G I x x J x G I x G I

x G n G I

n_



).

( ) , ( ) , ( ) ( )) (1), ( ) ,

(G₁ x I G₂ x J ₃ x x²I G₁ x I G₂ x J ₄ x

I _n  _n



Proof. Proof by induction on n. If n=5, then by Theorems 1 and 3, and induction hypothesis, we have

= ) (2), ( ) , ( ( ) (3), ( ) (1), (

= ) , (5)

( G

₁

G

₂

x I G

₁

x I G

₂

x x I G

₁

x I G

₂

x

I 

) , ( ) (1), ( ( ) (1), ( ) (1), ( ) (1

=  x I G

₁

x I G

₂

x  x I G

₁

x I G

₂

x

).

, ( ) , ( )) (1), ( ) ,

(G₁ x I G₂ x x²I G₁ x I G₂ x

I 



So the theorem is true for n=5. Now suppose that the result is true for less than n and we prove it for n. By Theorems 1 and 3, and induction hypothesis, we have

= ) 3), ( ( ) , ( ( ) 2), ( ( ) (1), (

= ) , ) ( (

2 1

2 1

2 1

x n G I x G I x x n G I x G I

x G n G I







) , ( ) (1), ( ( ) ( ) (1), ( ) (1),

( G

₁

x I G

₂

x J

₂

x x I G

₁

x I G

₂

x

I

_n



).

( ) , ( ) , ( ) ( )) (1), ( ) ,

(G₁ x I G₂ x J ₃ x x²I G₁ x I G₂ x J ₄ x

I _n  _n

 _▄

Theorem 3 implies that all forms of G1(m)G₂ have the same independence polynomials.

As application of Theorem 3, we obtain the following formula:

Corollary 2 .

1. The independence polynomial of path

P

_n is

2 . 2 2

1 2

= ) (

= ) , (

2 1

1

=

2





 





 

 

 





n

x s x

x J x P I

n

s n

n

cos



2. The independence polynomial of cycle C_n (n2) is

).

( )

(

= ) ,

( C x J

₁

x xJ

₁

x I

_{n n}



_n Proof.

1. By using Theorem 1, for

G =K

₁, we have

) , ( ) ( )

(1), ( ) (

= ) ), ( (

= ) ,

( P

₁

x I K

₁

n x J x I K

₁

x xJ

₁

x I K

₁

x

I

_{n n}



_n

) ( )

( )

( ) 2 (1

=  x J_n x xJ_n1 x x²J_n1 x

)

( )

(

= J

_n2

x  xJ

_n1

x ).

(

= J

_n3

x

So we have the result.

2. It follows from Theorems 1 and Part 1. ▄

References

[1] S. Alikhani, M.A. Iranmanesh, Digest Journal of Nanomaterials and Biostructures 5, (1), 1 (2010).

[2] S. Barnard, J.F. Child, Higher-Algebra, Macmillan, London, (1955).

[3] I. Gutman, F. Harary, Utilitas Mathematica 24 (1983)97-106.

[4] R. Frucht, F. Harary, Aequationes Math, (1970); 4, 322-324.

[5] C. Hoede, X. Li, Discrete Math. 25 (1994), 219-228.

[6] T. Koshy, Fibonacci, Lucas Numbers with Applications, A Wiley-Interscience Series of Texts, (2001).