TAILIEUCHUNG - Báo cáo khoa học:Perfect Matching Preservers

A subset M E(G) of the edge set E(G) of a graph G is called a matching provided that no two edges in M have a vertex in common. A perfect matching M is a matching with the property that each vertex of G is incident with an edge in M. For k a positive integer, a graph G is k-extendable provided that G has a matching of size k and every matching in G of size at most k can be extended to a perfect matching in G. | Perfect Matching Preservers Richard A. Brualdi Department of Mathematics University of Wisconsin - Madison Madison WI 53706 USA brualdi@ Martin Loebl Department of Applied Mathematics Institute for Theoretical Computer Science Charles University Malostranske namesti 25 118 00 Prague Czech Republic loebl@ Ondrej Pangrac Department of Applied Mathematics Institute for Theoretical Computer Science Charles University Malostranske namesti 25 118 00 Prague Czech Republic pangrac@ Submitted Nov 15 2004 Accepted Oct 19 2006 Published Oct 31 2006 AMS Subject Classification 05C20 05C50 05C70 Abstract For two bipartite graphs G and G a bijection p E G E G0 is called a perfect matching preserver provided that M is a perfect matching in G if and only if p M is a perfect matching in G . We characterize bipartite graphs G and G0 which are related by a matching preserver and the matching preservers between them. Supported by Ministry of Education of Czech Republic as project LN00A056. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R95 1 1 Introduction A subset M c E G of the edge set E G of a graph G is called a matching provided that no two edges in M have a vertex in common. A perfect matching M is a matching with the property that each vertex of G is incident with an edge in M. For k a positive integer a graph G is k-extendable provided that G has a matching of size k and every matching in G of size at most k can be extended to a perfect matching in G. In this paper we characterize the bipartite graphs G and G0 that are related by a matching preserver and so with appropriate labeling of edges have the same perfect matchings. We will achieve this by a full description of matching preservers defined as follows A bijection f E G E G0 is matching preserving or is a matching preserver provided that M is a perfect matching in G if and only if f M is a perfect matching in G0. Matching preservers for bipartite graphs G were investigated in 2

• Báo cáo khoa học
• Matching Preservers
• perfect matching
• hypoxanthine will
• xanthine oxidase
• radiotherapy
• antineoplastic
• scientific reports
• scientific research
• Research methods
• Data collection methods
• Understanding scientific research
• Ensuring research validity
• Measurement techniques
• Sampling methods
• Scientific research capacity
• Educational institutions
• Policy and management studies
• Vietnam Academy for Ethnic minorities
• Scientific bases
• earth sciences
• Research
• VNU Journal of Science
• Action research
• linguistics
• research projects
• Foreign Languages
• cooperative research
• Renewable energy
• Introduction to research
• Scientific investigation
• Scientific investigation research
• Experimental designs
• Measurement of variables
• Reading research
• Conducting and reading research
• Research process
• Research report
• Purpose of research
• Scientific method
• Conducting research
• The effect of university autonomy on training and scientific research
• Vietnam national university of agriculture
• Training and scientific research
• Vascular plant
• Flora
• Yen Tu
• Quang Ninh Research Forest
• statements and documents scientific reports
• medical reports
• medical knowledge
• medical research
• clinical trials
• medical management
• health care
• Methods in behavioral research
• Behavioral research
• Scientific understanding
• Fundamental research issues
• Measurement concepts
• Observational methods
• reading comprehension
• education
• optimal picket
• model creation
• urban expansion
• organizing spatial
• Journal of Science
• Journal of Technology
• Technology Management
• Research quality
• Strategy and policy
• Summary of Doctoral thesis
• Summary of Doctoral thesis in public Management
• State management
• Female scientific research human
• Research human resource development
• Scientific research and teaching
• Defense and security education
• Current situation and solutions
• Security education
• Structural biochemistry
• epigenetics
• MicroRNAs
• Tạp chí khoa học
• Tạp chí Công nghệ
• Quản lý công nghệ
• Human resources
• Science management
• Poliomyelitis vaccine Research
• Non Ri Maprec
• Production center