Mathematics – Combinatorics
Scientific paper
2009-12-21
Mathematics
Combinatorics
13 pages, 6 figures
Scientific paper
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 \not = 0$. This motivates us to investigate the structure of $\theta$-super positive graphs in this paper. Though a 0-super positive graph may not contain any cycle, we show that a $\theta$-super positive graph with $\theta \not = 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.
Ku Cheng Yeaw
Wong Kok Bin
No associations
LandOfFree
Properties of $θ$-super positive graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Properties of $θ$-super positive graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Properties of $θ$-super positive graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-301906