0
$\begingroup$

My apologies for the horribly worded title, I'm not sure how to describe this.

Learning about bipartite graphs in discrete math and I noticed this when testing a few cycle graphs. For $n$ even, $C_n$ can have two graphs $C_{n/2}$ inscribed within, which connect the two bipartitioned sets.

See examples here for $C_6$, $C_8$, and $C_{10}$. (the last one is hard to see, but it does have two pentagons inscribed within it) So $C_6$ has a $C_3$ that connects the nodes of one of its bipartitioned sets, and another $C_3$ connecting the nodes in the other set.

Is there a name for this property/feature/whatever?

$\endgroup$
2
  • $\begingroup$ I'm not sure I understand what property/feature you are referring to. As you have noted, the even cycle $C_{2k}$ is bipartite, which each part being an independent set of size $k$. Hence you could fit a cycle $C_k$ into each part, but you could also fit any graph on $k$ vertices into each part. $\endgroup$
    – Shagnik
    Jul 4, 2016 at 21:19
  • $\begingroup$ @Shagnik thanks for the feedback, I just wasn't sure how to word the question. I was focusing on cycles specifically and it just seemed interesting that we can nest a cycle of exactly half size, so I was looking for some deeper connection. Which is obvious now that I look back on it, because that is just constructing a cycle for each partition, of which there are two. $\endgroup$
    – Dave
    Jul 4, 2016 at 22:06

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .