Properties of \(\theta\)-super positive graphs (Q426799): Difference between revisions

Summary: 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.