Properties of θ-super positive graphs

الأصل · EN

Let the matching polynomial of a graph G be denoted by μ(G,x). A graph G is said to be θ-super positive if μ(G,θ)≠ 0 and μ(G v,θ)=0 for all v∈ 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 θ-super positive graphs for θ = 0. This motivates us to investigate the structure of θ-super positive graphs in this paper. Though a 0-super positive graph may not contain any cycle, we show that a θ-super positive graph with θ = 0 must contain a cycle. We introduce two important types of θ-super positive graphs, namely θ-elementary and θ-base graphs. One of our main results is that any θ-super positive graph G can be constructed by adding certain type of edges to a disjoint union of θ-base graphs; moreover, these θ-base graphs are uniquely determined by G. We also give a characterization of θ-elementary graphs: a graph G is θ-elementary if and only if the set of all its θ-barrier sets form a partition of V(G). Here, θ-elementary graphs and θ-barrier sets can be regarded as θ-analogue of elementary graphs and Tutte sets in classical matching theory.