Matching extension in prism graphs

作者：Aldred R E L^*; Plummer Michael D

来源：Discrete Applied Mathematics, 2017, 221: 25-32.

DOI：10.1016/j.dam.2016.12.017

• Prism graph
• Matching
• Matching extension
• Bicritical
• Factor-critical
• E(m, n)

If G is any graph, the prism graph of G, denoted P(G), is the cartesian product of G with a single edge, or equivalently, the graph obtained by taking two copies of G, say G(1) and G(2), with the same vertex labelings and joining each vertex of G(1) to the vertex of G(2) having the same label by an edge. A connected graph G has property E(m, n) (or more briefly "G is E(m, n)") if for every pair of disjoint matchings M and N in G with vertical bar M vertical bar = m and vertical bar N vertical bar = n respectively, there is a perfect matching F in G such that M subset of F and N boolean AND F = phi. A graph which has the E(m, 0) property is also said to be m-extendable. In this paper, we begin the study of the E(m, n) properties of the prism graph P(G) when G is an arbitrary graph as well as the more special situations when, in addition, G is bipartite or bicritical.

• 出版日期2017-4-20