A simple proof of an inequality connecting the alternating number of independent sets and the decycling number |
| |
Authors: | Vadim E Levit Eugen Mandrescu |
| |
Institution: | aAriel University Center of Samaria, Israel;bHolon Institute of Technology, Israel |
| |
Abstract: | If sk denotes the number of independent sets of cardinality k and α(G) is the size of a maximum independent set in graph G, then I(G;x)=s0+s1x+?+sα(G)xα(G) is the independence polynomial of G (Gutman and Harary, 1983) 8].In this paper we provide an elementary proof of the inequality|I(G;−1)|≤2φ(G) (Engström, 2009) 7], where φ(G) is the decycling number of G (Beineke and Vandell, 1997) 3], namely, the minimum number of vertices that have to be deleted in order to turn G into a forest. |
| |
Keywords: | Independent set Independence polynomial Decycling number Forest Cyclomatic number |
本文献已被 ScienceDirect 等数据库收录! |
|