0
$\begingroup$

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 vertices. If not, which indpendence induced subgraphs of powers of cycles have a distinct 1-factor?

I believe that all odd powers of even order cycles have all their independence induced subgraphs each having a 1-factor. This is because, perfect matchings can be taken by pairing two maximal independent sets of vertices(considering independent edges between them). However, I doubt it for the case of even powers of cycles. Consider the power of cycle $C_8^2$, the second power of cycle on $8$ vertices . Here, we label the vertices from $0$ to $7$ and the maximal independent sets of vertices are $[0,4], [1,5], [2,6], [3,7]$, where the two independent vertices are put in one independent set of square brackets. The edges, of which there are $16$ are $(01), (60),(70), (02);(71), (12), (13), (23), (24), (34), (35), (45), (46), (56), (57), (67)$, where the two numbers in brockets dente the edge joining the left numbered vertex to right numbered vertex. If we consider the induced subgraph formed by deleting the vertices $[3,7]$, we see that the induced subgraph seems not to have a distinct(all independent edges distinct from previous 1-factors of independent induced subgraphs) 1-factor. Any light on this observation? Thanks beforehand.

Improve this question
$\endgroup$
4
  • $\begingroup$ The graph should be regular and have a even numbers of vertices. $\endgroup$
    – LeechLattice
    Commented May 3, 2019 at 8:53
  • $\begingroup$ @Bullet51 Yes, powers of cycles are regular(cayley), and of even degree . So do you mean to say that all even powers of cycles have 1-factorizable independence induced subgraphs? My $C_8^2$ example shows that this may not be the case $\endgroup$
    – vidyarthi
    Commented May 3, 2019 at 8:55
  • $\begingroup$ These are meant to be necessary conditions for 1-factors to exist. See the Wikipedia article for that. $\endgroup$
    – LeechLattice
    Commented May 3, 2019 at 8:57
  • $\begingroup$ @Bullet51 thanks for that. Slightly modified the question $\endgroup$
    – vidyarthi
    Commented May 3, 2019 at 9:02

0

Reset to default

You must log in to answer this question.