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


Odd subgraphs and matchings
Authors:M Kano  Gyula Y Katona  
Institution:

a Department of Computer and Information Sciences, Ibaraki University, Nakanarusawa, Hitachi, 316-8511 Japan

b Department of Computer and Information Sciences, Budapest University of Technology and Economics, Budapest, Pob.: 91, 1521, Hungary

Abstract:Let G be a graph and f : V(G)→{1,3,5,…}. Then a subgraph H of G is called a (1,f)-odd subgraph if degH(x)set membership, variant{1,3,…,f(x)} for all xset membership, variantV(H). If f(x)=1 for all xset membership, variantV(G), then a (1,f)-odd subgraph is nothing but a matching. A (1,f)-odd subgraph H of G is said to be maximum if G has no (1,f)-odd subgraph K such that |K|>|H|. We show that (1,f)-odd subgraphs have some properties similar to those of matchings, in particular, we give a formula for the order of a maximum (1,f)-odd subgraph, which is similar to that for the order of a maximum matching.
Keywords:Odd subgraph  Graph factor  Matching
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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