Skip to main content
Dumb me, meant edges
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Edit Tony's answer is quite nice, but I meant something else. Sorry for editing again, I meant edges.

I am looking for a graph with 3 distinguished vertices of degreeedges $1$$xx'$,$yy'$,$zz'$ where $\deg(x)=\deg(y)=\deg(z)=1$. One

One can chose arbitrary weights for the edges and the graph must satisfy:

  1. Must have at least two maximum weighted matchings in one of which all of the 3 distinguished verticesedges are present and in the other all are not present.
  2. For all maximum weighted matchings (if more than 2) the distinguished verticesedges are either all present or all not present.

Need this for a graph gadget and suspect it is quite unlikely to exist.

For only 2 distinguished verticesedges a trivial solution is the path with 3 edges $v v' v'' v'''$.

I am looking for a graph with 3 distinguished vertices of degree $1$. One can chose arbitrary weights for the edges and the graph must satisfy:

  1. Must have at least two maximum weighted matchings in one of which all of the 3 distinguished vertices are present and in the other all are not present.
  2. For all maximum weighted matchings (if more than 2) the distinguished vertices are either all present or all not present.

Need this for a graph gadget and suspect it is quite unlikely to exist.

For only 2 distinguished vertices a trivial solution is the with 3 edges $v v' v'' v'''$.

Edit Tony's answer is quite nice, but I meant something else. Sorry for editing again, I meant edges.

I am looking for a graph with 3 distinguished edges $xx'$,$yy'$,$zz'$ where $\deg(x)=\deg(y)=\deg(z)=1$.

One can chose arbitrary weights for the edges and the graph must satisfy:

  1. Must have at least two maximum weighted matchings in one of which all of the 3 distinguished edges are present and in the other all are not present.
  2. For all maximum weighted matchings (if more than 2) the distinguished edges are either all present or all not present.

Need this for a graph gadget and suspect it is quite unlikely to exist.

For only 2 distinguished edges a trivial solution is the path with 3 edges $v v' v'' v'''$.

Corrected the path with 3 edges
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

I am looking for a graph with 3 distinguished vertices of degree $1$. One can chose arbitrary weights for the edges and the graph must satisfy:

  1. Must have at least two maximum weighted matchings in one of which all of the 3 distinguished vertices are present and in the other all are not present.
  2. For all maximum weighted matchings (if more than 2) the distinguished vertices are either all present or all not present.

Need this for a graph gadget and suspect it is quite unlikely to exist.

For only 2 distinguished vertices a trivial solution is the pathwith 3 edges $v v' v''$$v v' v'' v'''$.

I am looking for a graph with 3 distinguished vertices of degree $1$. One can chose arbitrary weights for the edges and the graph must satisfy:

  1. Must have at least two maximum weighted matchings in one of which all of the 3 distinguished vertices are present and in the other all are not present.
  2. For all maximum weighted matchings (if more than 2) the distinguished vertices are either all present or all not present.

Need this for a graph gadget and suspect it is quite unlikely to exist.

For only 2 distinguished vertices a trivial solution is the path $v v' v''$.

I am looking for a graph with 3 distinguished vertices of degree $1$. One can chose arbitrary weights for the edges and the graph must satisfy:

  1. Must have at least two maximum weighted matchings in one of which all of the 3 distinguished vertices are present and in the other all are not present.
  2. For all maximum weighted matchings (if more than 2) the distinguished vertices are either all present or all not present.

Need this for a graph gadget and suspect it is quite unlikely to exist.

For only 2 distinguished vertices a trivial solution is the with 3 edges $v v' v'' v'''$.

Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Would a graph with such maximum weighted matchings exist?

I am looking for a graph with 3 distinguished vertices of degree $1$. One can chose arbitrary weights for the edges and the graph must satisfy:

  1. Must have at least two maximum weighted matchings in one of which all of the 3 distinguished vertices are present and in the other all are not present.
  2. For all maximum weighted matchings (if more than 2) the distinguished vertices are either all present or all not present.

Need this for a graph gadget and suspect it is quite unlikely to exist.

For only 2 distinguished vertices a trivial solution is the path $v v' v''$.