0
$\begingroup$

Let $G$ be a regular simple graph with degree $\Delta=n-k-1$ and order $m$. Let $C_k$ be the regular graph which is formed by removing a $k$-factor from the complete graph $K_{n}$. I think we could always find a proper induced subgraph of $C_k$ with maximum degree at least $\ge\frac{\Delta}{2}$ as a subgraph of the graph $G$. Is this true?

If this be true, then I think to find the invariants of $G$, it suffices to find the invariants of $C_k$. Then, the invariants of $G$ would be related linearly with that of $C_k$. For example, the chromatic number/ index seems to be closely related to the number of disjoint copies of $C_k$ which occurs as an induced graph and $m$. In a way, I think this could be related to the tree-decomposition of the graph $G$. Any light on this? Thanks beforehand.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ There is more than one graph that can be obtained from $K_n$ by removing a $k$-factor (for $k = 2$, e.g. removing a Hamilton cycle vs removing two disjoint cycles covering all vertices gives different graphs). Neither of these graphs is a subgraph of the other. $\endgroup$
    – Florian Lehner
    Commented Jul 29, 2020 at 10:46
  • $\begingroup$ @FlorianLehner thanks! so for regular graphs which contain certain copies of $C_k$ with a removal of a fixed $k$ factor, can we relate the graph invariant of $G$ with that of $C_k$? $\endgroup$
    – vidyarthi
    Commented Jul 29, 2020 at 11:36
  • 2
    $\begingroup$ I don't get it. $G$ and $C_k$ are both regular graphs of degree $\Delta$, so one can't be an induced subgraph of the other unless they are equal. I suspect you are not asking the question you intend to ask. $\endgroup$
    – Brendan McKay
    Commented Jul 29, 2020 at 12:18
  • $\begingroup$ @BrendanMcKay thanks! edited the post. The comment by Florian answers my main question anyways. $\endgroup$
    – vidyarthi
    Commented Jul 29, 2020 at 12:20
  • 2
    $\begingroup$ It makes sense, but the answer is "no". The simplest example is if $\Delta=k$ then $C_k$ could be the complement of $G$ and so have no edges in common with $G$. If $\Delta$ is not far from $k$, it can still be true that $C_k$ and $G$ have too few common edges. $\endgroup$
    – Brendan McKay
    Commented Jul 29, 2020 at 14:22

1 Answer 1

Reset to default
3
$\begingroup$

The answer is no.

Let $G$ be the Hoffman-Singleton graph (hence n=50, k=42). Let $C_k$ be the disjoint union of 5 $K_8$s and a $K_{10}-C$ ($K_{10}$ with a 10-cycle removed). Any proper induced subgraph of $C_k$ with maximum degree at least 4 will contain a $C_3$ or $C_4$, which $G$ does not contain.

Improve this answer
$\endgroup$

You must log in to answer this question.

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