Properties of -super positive graphs

MaRDI QIDQ426799zbMATH OpenFDO

Authors Cheng Yeaw Ku, K. B. Wong

Publication date 12 June 2012

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

Full work available at URL https://arxiv.org/abs/0912.4100, http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i1p37

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

zbMATH Keywords

barrier setselementary graphextreme setsGallai-Edmonds decompositionmatching polynomial

Mathematics Subject Classification ID

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

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.

Review text

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.

Recommendations

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

Cited in

(4)

• 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
• Extensions of barrier sets to nonzero roots of the matching polynomial

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)