Parity and disparity subgraphs |
| |
Authors: | Terry A. McKee Lutz Volkmann |
| |
Affiliation: | 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 等数据库收录! |
|