Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with perfect-matchings
Search options not deleted
user 100231
A perfect matching is a matching of all the vertices of a graph. In other words, a perfect matching is a set of edges such that each vertex of the graph is incident to exactly one edge in the set.
0
votes
0
answers
107
views
Bound on the number of maximum matchings in a graph
It is known that the number of perfect matchings in a graph is bounded above by the integer part of the square root of the permanent of its adjacency matrix. But, suppose I take the square root of the …
- 2,089
0
votes
1
answer
148
views
Combining three matchings to form a maximal matching
Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.
Now, is there a way to choos …
- 2,089
0
votes
Accepted
Combining three matchings to form a maximal matching
Such a matching cannot be said to exist if the maximum degree of the bipartite graphs $A\cup B$, $B\cup C$ and $C\cup A$ are the same as that of the whole graph. This is because, if the individual bip …
- 2,089
0
votes
1
answer
352
views
A vertex transitive graph has a near perfect/ matching missing an independent set of vertices
Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove an i …
- 2,089
1
vote
Accepted
A vertex transitive graph has a near perfect/ matching missing an independent set of vertices
Yes, it is possible to find a perfect/near perfect matching in the case of powers of cycles when one non-singleton set of maximal independent vertices of the given form is removed. This is because, th …
- 2,089
2
votes
1
answer
328
views
Number of distinct perfect matchings/near perfect matchings in an induced subgraph
Consider a Class 1 graph with degree $\Delta\ge3$ and the induced subgraph formed by deleting a set of independent vertices of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$. Then, what is th …
- 2,720
0
votes
0
answers
54
views
Do all induced subgraphs of powers of cycles have a perfect matching
Do all independence induced subgraphs of powers of cycles have a distinct 1-factor? By independence induced, I mean those induced subgraphs which are formed by removing a maximal independent set of ve …
- 2,089