On defect-d matchings in graphs |
| |
Authors: | Charles HC Little Douglas D Grant DA Holton |
| |
Institution: | Royal Melbourne Institute of Technology, Melbourne, Vic. 3000, Australia;University of Reading, Reading, England;University of Melbourne, Parkville, Vic. 3052, Australia |
| |
Abstract: | A defect-d matching in a graph G is a matching which covers all but d vertices of G. G is d-covered if each edge of G belongs to a defect-d matching. Here we characterise d-covered graphs and d-covered connected bipartite graphs. We show that a regular graph G of degree r which is (r ? 1)-edge-connected is 0-covered or 1-covered depending on whether G has an even or odd number of vertices, but, given any non-negative integers r and d, there exists a graph regular of degree r with connectivity and edge-connectivity r ? 2 which does not even have a defect-d matching. Finally, we prove that a vertex-transitive graph is 0-covered or 1-covered depending on whether it has an even or odd number of vertices. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|