
Cheng Yeaw Ku

Kok Bin Wong
Abstract
Let the matching polynomial of a graph $G$ be denoted by $\mu (G,x)$. A graph $G$ is said to be $\theta$super positive if $\mu(G,\theta)\neq 0$ and $\mu(G\setminus v,\theta)=0$ for all $v\in V(G)$. In particular, $G$ is $0$super positive if and only if $G$ has a perfect matching. While much is known about $0$super positive graphs, almost nothing is known about $\theta$super positive graphs for $\theta \neq 0$. This motivates us to investigate the structure of $\theta$super positive graphs in this paper. Though a $0$super positive graph need not contain any cycle, we show that a $\theta$super positive graph with $\theta \neq 0$ must contain a cycle. We introduce two important types of $\theta$super positive graphs, namely $\theta$elementary and $\theta$base graphs. One of our main results is that any $\theta$super positive graph $G$ can be constructed by adding certain type of edges to a disjoint union of $\theta$base graphs; moreover, these $\theta$base graphs are uniquely determined by $G$. We also give a characterization of $\theta$elementary graphs: a graph $G$ is $\theta$elementary if and only if the set of all its $\theta$barrier sets form a partition of $V(G)$. Here, $\theta$elementary graphs and $\theta$barrier sets can be regarded as $\theta$analogue of elementary graphs and Tutte sets in classical matching theory.