On the structure of minimally n-extendable bipartite graphs

✍ Scribed by Dingjun Lou

• Book ID: 104114205
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 521 KB
• Volume: 202
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(98)00291-x

✦ Synopsis

It is proved that, in a minimal n-extendable bipartite graph, the subgraph induced by the edges both ends of which have degree at least n + 2 is a forest. As a consequence, every minimal n-extendable bipartite graph has at least 2n + 2 vertices of degree n + 1. This result is sharp. Some other structural results on minimally n-extendable bipartite graphs are also given.