Skip to main content
MathOverflow

Return to Question

added 44 characters in body
Source Link
vidyarthi
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form a triangle?

For Odd graphs ofOdd graphs having $n-k\ge3$$(n-k)\ge3$, as these are triangle free, the answer would be none. But, suppose $n=7a,k=2a$, for positive $a$. Then, is it possible to say that these contain all even cycles of order $\ge12$ such that any three consecutive vertices induce a triangle? A more stronger version would be, if the square (in the distance sense) of any cycle of order $\ge12$ is an induced subgraph of the Kneser graphs $G$ with $n=7a,k=2a$? Any hints?

Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form a triangle?

For Odd graphs of having $n-k\ge3$, as these are triangle free, the answer would be none. But, suppose $n=7a,k=2a$, for positive $a$. Then, is it possible to say that these contain all even cycles of order $\ge12$ such that any three consecutive vertices induce a triangle? Any hints?

Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form a triangle?

For Odd graphs having $(n-k)\ge3$, as these are triangle free, the answer would be none. But, suppose $n=7a,k=2a$, for positive $a$. Then, is it possible to say that these contain all even cycles of order $\ge12$ such that any three consecutive vertices induce a triangle? A more stronger version would be, if the square (in the distance sense) of any cycle of order $\ge12$ is an induced subgraph of the Kneser graphs $G$ with $n=7a,k=2a$? Any hints?

Source Link
vidyarthi
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

Cycles in Kneser graphs with three vertices forming triangles

Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form a triangle?

For Odd graphs of having $n-k\ge3$, as these are triangle free, the answer would be none. But, suppose $n=7a,k=2a$, for positive $a$. Then, is it possible to say that these contain all even cycles of order $\ge12$ such that any three consecutive vertices induce a triangle? Any hints?