Properties of \(\theta\)-super positive graphs

Cheng Yeaw Ku ; Kok Bin Wong

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

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.

Détail

DOI : 10.37236/2041

Classification : 05C31, 05C70, 05D05
Mots-clés : matching polynomial, Gallai-Edmonds decomposition, elementary graph, barrier sets, extreme sets