错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Perfect Pseudo-Matchings in Cubic Graphs

  • Herbert Fleischner,
  • Behrooz Bagheri Gh,
  • Benedikt Klocker

摘要

A perfect pseudo-matching M in a cubic graph G is a spanning subgraph of G such that every component of M is isomorphic to \(K_2\) K 2 or to \(K_{1,3}\) K 1 , 3 . In view of snarks G with dominating cycle C, this is a natural generalization of perfect matchings since \(G \setminus E(C)\) G \ E ( C ) is a perfect pseudo-matching. Of special interest are such M where G/M is planar because such G have a cycle double cover. We show that various well known classes of snarks contain planarizing perfect pseudo-matchings, and that there are at least as many snarks with planarizing perfect pseudo-matchings as there are cyclically \(5-\) 5 - edge-connected snarks.