Properties of -super positive graphs

zbMATH Open1243.05117arXiv0912.4100MaRDI QIDQ426799FDOQ426799

Authors: Cheng Yeaw Ku, K. B. Wong 

Publication date: 12 June 2012

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/0912.4100

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Generalized \(D\)-graphs for nonzero roots of the matching polynomial
• Algebraic matching theory
• The order of matching energy and Hosoya index of \(\theta \)-graphs
• Generalizing Tutte's theorem and maximal non-matchable graphs
• Extensions of barrier sets to nonzero roots of the matching polynomial

zbMATH Keywords

matching polynomialextreme setsGallai-Edmonds decompositionbarrier setselementary graph

Mathematics Subject Classification ID

Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05)

Cited In (4)

• Extensions of barrier sets to nonzero roots of the matching polynomial
• A refined Gallai-Edmonds structure theorem for weighted matching polynomials
• Gallai-Edmonds structure theorem for weighted matching polynomial
• Generalizing Tutte's theorem and maximal non-matchable graphs

This page was built for publication: Properties of \(\theta\)-super positive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426799)