首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Parity and disparity subgraphs
Authors:Terry A McKee  Lutz Volkmann
Institution:a Department of Mathematics & Statistics, Wright State University, Dayton, OH 45435, USA
b Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Abstract:A parity subgraph of a graph is a spanning subgraph such that the degrees of each vertex have the same parity in both the subgraph and the original graph. Known results include that every graph has an odd number of minimal parity subgraphs. Define a disparity subgraph to be a spanning subgraph such that each vertex has degrees of opposite parities in the subgraph and the original graph. (Only graphs with all even-order components can have disparity subgraphs). Every even-order spanning tree contains both a unique parity subgraph and a unique disparity subgraph. Moreover, every minimal disparity subgraph is shown to be paired by sharing a spanning tree with an odd number of minimal parity subgraphs, and every minimal parity subgraph is similarly paired with either one or an even number of minimal disparity subgraphs.
Keywords:Parity subgraph  Parity factor  Even factor  Odd factor  Disparity subgraph  Disparity factor
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号