Source author record

Ohr Kadrawi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Linear Algorithm for Computing Independence Polynomials of Trees

An independent set in a graph is a set of pairwise non-adjacent vertices. Let $α(G)$ denote the cardinality of a maximum independent set in the graph $G = (V, E)$ . Gutman and Harary defined the independence polynomial of $G$ $I(G;x) = \sum_{k=0}^{α(G)}{s_k}x^{k}={s_0}+{s_1}x+{s_2}x^{2}+...+{s_{α(G)}}x^{α(G)},$ where $s_k$ denotes the number of independent sets of cardinality $k$ in the graph $G$ . A comprehensive survey on the subject is due to Levit and Mandrescu, where some recursive formulas are allowing to calculate the independence polynomial. A direct implementation of these recursions does not bring about an efficient algorithm. Yosef, Mizrachi, and Kadrawi developed an efficient way for computing the independence polynomials of trees with $n$ vertices, such that a database containing all of the independence polynomials of all the trees with up to $n-1$ vertices is required. This approach is not suitable for big trees, as an extensive database is needed. On the other hand, using dynamic programming, it is possible to develop an efficient algorithm that prevents repeated calculations. In summary, our dynamic programming algorithm runs over a tree in linear time and does not depend on a database.

preprint2022arXiv

On Unimodality of Independence Polynomials of Trees

An independent set in a graph is a set of pairwise non-adjacent vertices. The independence number $α{(G)}$ is the size of a maximum independent set in the graph $G$ . The independence polynomial of a graph is the generating function for the sequence of numbers of independent sets of each size. In other words, the $k$ -th coefficient of the independence polynomial equals the number of independent sets comprised of $k$ vertices. For instance, the degree of the independence polynomial of the graph $G$ is equal to $α{(G)}$ . In 1987, Alavi, Malde, Schwenk, and Erd{ö}s conjectured that the independence polynomial of a tree is unimodal. In what follows, we provide support to this assertion considering trees with up to $20$ vertices. Moreover, we show that the corresponding independence polynomials are log-concave and, consequently, unimodal. The algorithm computing the independence polynomial of a given tree makes use of a database of non-isomorphic unlabeled trees to prevent repeated computations.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.