# All Questions

Tagged with graph-theory perfect-matchings

53
questions

**0**

votes

**1**answer

58 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 ...

**1**

vote

**0**answers

78 views

### A simple case of a strong version of the Berge-Fulkerson conjecture

UPDATE 28 June 2019 A counterexample for Conjecture 2 has been provided. The conjecture is now demoted again to guess. The text has been updated to reflect this change, and there is now a new ...

**1**

vote

**0**answers

19 views

### Perfect matchings and edge cuts in cubic graphs - part 1

Let $G$ be a bridgeless cubic (simple) graph, and let $M$ be a perfect matching in $G$. $G-M$ will necessarily be a set of circuits. For example, if we delete a perfect matching from $K_{3,3}$ we ...

**1**

vote

**1**answer

51 views

### Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph

What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am ...

**2**

votes

**1**answer

52 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 ...

**0**

votes

**0**answers

35 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 ...

**6**

votes

**0**answers

267 views

### Has this notion of vertex-coloring of graphs been studied?

In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-...

**17**

votes

**1**answer

722 views

### Vertex Coloring inherited from Perfect Matchings (motivated by Quantum Physics)

The following purely graph-theoretic question is motivated by quantum mechanics (and a special case of the questions asked here).
Bi-Colored Graph: A bi-colored weighted graph $G=(V(G),E(G))$, on $n$ ...

**0**

votes

**0**answers

14 views

### Name for Spanning Trees Containing all Edges of a Minimum Weight Perfect Matching

This question is motivated by the task of "uniformly" bicoloring the vertices of a symmetric TSP-instance graph with $2n$ vertices.
A simple heuristical requirement for such a bicoloring could be ...

**7**

votes

**1**answer

182 views

### Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?

The sequence A006318 at OEIS stands for the Schr?der numbers.
They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, ...

**2**

votes

**0**answers

33 views

### Can Orientability of Manifolds be Generalized to TSP Instances?

It is well known, that there are two basic kinds of manifolds, orientable and non-orientable ones; the most simple examples being obtained by identifying a pair of opposite sides of a rectangular ...

**6**

votes

**1**answer

105 views

### Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?

In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...

**11**

votes

**1**answer

445 views

### Graphs with only disjoint perfect matchings, with coloring

The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...

**-2**

votes

**1**answer

341 views

### Infinite graphs with large degree but no perfect matching [duplicate]

Is there an example of an infinite connected, simple, undirected graph $G = (V,E)$ such that every vertex has $|V|$ neighbors, but $G$ does not have a perfect matching (that is, a set $M\subseteq E$ ...

**9**

votes

**2**answers

241 views

### How to characterize “matching-transitive” regular graphs?

I am interested in regular graphs $G$ such that for each pair of 1-factors (=perfect matchings) $F$ and $F'$ there is an automorphism of $G$ that takes $F$ to $F'$. Let's call this property matching ...