2
$\begingroup$

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 the number of disjoint near perfect matchings(when the induced subgraph is odd) or perfect matchings(when the induced subgraph is even) which cover the edges of the graph maximally?

The same question for Class 2 graphs, is, what is the number of disjoint near-perfect matchings or perfect matchings of the induced subgraph formed by deleting an independent set of vertices that cover the edges of the graph maximally?

Subquestion: What if the graph were to be a power of cycles, or, a circulant graph?

I feel that on removal of an independent set of vertices(of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$), the number of disjoint near perfect matchings in a Class 1(or atleast powers of cycles) is atleast $\Delta-2$. Is this true?, or, are there any counterexamples? Is the matching polynomial of any use here? I think the matching generating polynomial gives the number of distinct perfect matchings but they do not take into consideration whether the edges of graph are covered or not. For example, the complete graph on six vertices is said to have $15$ distinct perfect matchings. But, only $5$ distinct perfect matchings are sufficient to cover the graph maximally(covers all edges). So, the maximal matchings I discuss here are disjoint and sort of nearly factorise the induced subgraph. I also think perfect matchings( or near-perfect matchings) of induced subgraphs of regular graphs can be thought of as permanents of the adjacency matrix of the induced subgraph. Can this approach be used? Thanks beforehand.

Improve this question
$\endgroup$
12
  • $\begingroup$ Do you mean max degree $Delta$ ... or regular degree $Delta$ ... or ??? $\endgroup$
    – EGME
    Commented May 15, 2019 at 8:48
  • $\begingroup$ @EGME actually I mean $\it{max}$ $\it{degree}$ $\Delta$, but regular is somewhat easier to answer, I think $\endgroup$
    – vidyarthi
    Commented May 15, 2019 at 8:50
  • 1
    $\begingroup$ Question. If we take the complete bipartite graph on 3+3=6 vertices ($K_{3,3}$) and we remove all the vertices on one side, the remaining graph has no edges (and hence no perfect matchings). How does this fit in with your question? $\endgroup$
    – Pat Devlin
    Commented May 15, 2019 at 16:06
  • 1
    $\begingroup$ Perhaps a silly question, but can’t we (easily?) find induced subgraphs with no perfect matchings? For instance, subgraphs with an odd number of vertices. And if you mean “maximal matchings” instead of perfect, we could probably find a subgraph where the degrees are too small. $\endgroup$
    – Pat Devlin
    Commented May 15, 2019 at 18:06
  • 1
    $\begingroup$ Still might be confused. Take the 3-regular graph on 16 vertices found here mathoverflow.net/questions/98385/…. You can remove an independent set of size 5 so as to split the graph up into a bunch of components of odd size, so it won’t have anything close to a perfect matching. In fact, for higher degree, you could probably make that example worse by having one cut vertex in the middle connected to a bunch of stuff. $\endgroup$
    – Pat Devlin
    Commented May 15, 2019 at 18:20

1 Answer 1

Reset to default
3
$\begingroup$

Instead of adding yet more comments, here’s an answer that might shoot down a lot of conjectures you might have hoped.

Consider the 4-regular circulant graph on 16 vertices where we connect vertices $x,y$ iff $x-y \in \{\pm 1, \pm 4\}$ (subtraction and vertex labels all viewed mod 16).

Then delete the vertices $\{0, 3,5, 8\}$, which is the neighborhood of the vertex $4$. After deleting this, we’re left with 12 vertices, which form two connected components (vertex 4 is isolated, and the other 11 vertices form a connected subgraph). This induced subgraph has no near-perfect matchings since it has two connected components of odd cardinality.

So whatever it is you might be hoping for, it’s probably false (except perhaps for powers of a cycle, for which there’s so much structure that there might not be much room for anything interesting to happen [haven’t thought too much about that case]). Let me know how this example fits in with whatever you were hoping for.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ the end of "conjecturitis", thanks $\endgroup$
    – vidyarthi
    Commented May 15, 2019 at 21:38
  • 2
    $\begingroup$ Hah. If you find a cure for that in general, let me know! I have a chronic case of that. $\endgroup$
    – Pat Devlin
    Commented May 15, 2019 at 21:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .