Properties of \(\theta\)-super positive graphs (Q426799): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0912.4100 / rank | |||
Normal rank |
Latest revision as of 14:35, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Properties of \(\theta\)-super positive graphs |
scientific article |
Statements
Properties of \(\theta\)-super positive graphs (English)
0 references
12 June 2012
0 references
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.
0 references
matching polynomial
0 references
Gallai-Edmonds decomposition
0 references
elementary graph
0 references
barrier sets
0 references
extreme sets
0 references