Construction and characterization of graphs whose each spanning tree has a perfect matching

MaRDI QIDQ6269929arXivFDO

Authors Baoyindureng Wu, Heping Zhang

Publication date 30 January 2016

Published in arXiv

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

arXiv classification

math.CO

Abstract: An edge subset $S$ of a connected graph $G$ is called an anti-Kekul'{e} set if $G-S$ is connected and has no perfect matching. We can see that a connected graph $G$ has no anti-Kekul'{e} set if and only if each spanning tree of $G$ has a perfect matching. In this paper, by applying Tutte's 1-factor theorem and structure of minimally 2-connected graphs, we characterize all graphs whose each spanning tree has a perfect matching In addition, we show that if $G$ is a connected graph of order $2n$ for a positive integer $ngeq4$ and size $m$ whose each spanning tree has a perfect matching, then $mleqfrac(n+1)n2$, with equality if and only if $Gcong{K}_{n}circ{K}_1$.

This page was built for publication: Construction and characterization of graphs whose each spanning tree has a perfect matching

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