Matching extension in prism graphs
| Autor: | Robert E. L. Aldred, Michael D. Plummer |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Factor-critical graph
Discrete mathematics Applied Mathematics Symmetric graph 010102 general mathematics 0102 computer and information sciences 01 natural sciences Simplex graph Combinatorics Vertex-transitive graph Edge-transitive graph Windmill graph 010201 computation theory & mathematics Graph power Discrete Mathematics and Combinatorics Bound graph 0101 mathematics Mathematics |
| Zdroj: | Discrete Applied Mathematics. 221:25-32 |
| ISSN: | 0166-218X |
| Popis: | 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 G1 and G2, with the same vertex labelings and joining each vertex of G1 to the vertex of G2 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 |M|=m and |N|=n respectively, there is a perfect matching F in G such that MF and NF=. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect