Graphs where each spanning tree has a perfect matching

Authors

  • Baoyindureng Wu
  • Heping Zhang

DOI:

https://doi.org/10.11575/cdm.v16i3.62279

Abstract

An edge subset S of a connected graph G is called an anti-Kekul\'{e} set if GS 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 note, we characterize all graphs where 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 n4 and size m whose each spanning tree has a perfect matching, then m(n+1)n/2, with equality if and only if GKnK1.

Downloads

Published

2021-12-31

Issue

Section

Articles