The graph of perfect matching polytope and an extreme problem |
| |
Authors: | Hong Bian |
| |
Institution: | a Department of Mathematics, Xinjiang Normal University, Urumqi, Xinjiang 830054, PR China b Department of Mathematics, Xiamen University, Xiamen, Fujian 361005, PR China |
| |
Abstract: | For graph G, its perfect matching polytope Poly(G) is the convex hull of incidence vectors of perfect matchings of G. The graph corresponding to the skeleton of Poly(G) is called the perfect matching graph of G, and denoted by PM(G). It is known that PM(G) is either a hypercube or hamilton connected D.J. Naddef, W.R. Pulleyblank, Hamiltonicity and combinatorial polyhedra, J. Combin. Theory Ser. B 31 (1981) 297-312; D.J. Naddef, W.R. Pulleyblank, Hamiltonicity in (0-1)-polytope, J. Combin. Theory Ser. B 37 (1984) 41-52]. In this paper, we give a sharp upper bound of the number of lines for the graphs G whose PM(G) is bipartite in terms of sizes of elementary components of G and the order of G, respectively. Moreover, the corresponding extremal graphs are constructed. |
| |
Keywords: | Polytope Saturated graph Perfect matching graph |
本文献已被 ScienceDirect 等数据库收录! |
|