Skip to main content
added 7 characters in body
Source Link

The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and coclique (independent set) numbers respectively.

It is known, in particular, that the clique-coclique bound holds for all vertex-transitive graphs and distance-regular graphs - two families of walk-regular graphs.

The clique-coclique also appears to hold for all of the examples of walk-regular graphs that I know of that are neither vertex-transitive nor distance-regular. It is also apparent that the clique-coclique bound holds for some other families of walk-regular graphs, namely semi-symmetric graphs.

Could it be possible that the clique-coclique bound actually holds for all (connected) walk-regular graphs?

By informal reasoning in head, it feels plausible to me that this could be the case? I wonder what would might be a good approach to take to try to prove or disprove this?

The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and coclique (independent set) numbers respectively.

It is known, in particular, that the clique-coclique bound holds for all vertex-transitive graphs and distance-regular - two families of walk-regular graphs.

The clique-coclique also appears to hold for all of the examples of walk-regular graphs that I know of that are neither vertex-transitive nor distance-regular. It is also apparent that the clique-coclique bound holds for some other families of walk-regular graphs, namely semi-symmetric graphs.

Could it be possible that the clique-coclique bound actually holds for all (connected) walk-regular graphs?

By informal reasoning in head, it feels plausible to me that this could be the case? I wonder what would might be a good approach to take to try to prove or disprove this?

The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and coclique (independent set) numbers respectively.

It is known, in particular, that the clique-coclique bound holds for all vertex-transitive graphs and distance-regular graphs - two families of walk-regular graphs.

The clique-coclique also appears to hold for all of the examples of walk-regular graphs that I know of that are neither vertex-transitive nor distance-regular. It is also apparent that the clique-coclique bound holds for some other families of walk-regular graphs, namely semi-symmetric graphs.

Could it be possible that the clique-coclique bound actually holds for all (connected) walk-regular graphs?

By informal reasoning in head, it feels plausible to me that this could be the case? I wonder what would might be a good approach to take to try to prove or disprove this?

deleted 172 characters in body
Source Link

The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and coclique (independent set) numbers respectively.

It is known, in particular, that the clique-coclique bound holds for all vertex-transitive graphs and all distance-regular graphs - two families of walk-regular graphs.

The clique-coclique also appears to hold for all of the examples of walk-regular graphs that I know of that are neither vertex-transitive nor distance-regular  . It is also apparent that the clique- which includescoclique bound holds for some other families of walk-regular graphs that are not, namely semi-symmetric eithergraphs.

Could it be possible that the clique-coclique bound actually holds for all (connected) walk-regular graphs?

By informal reasoning in head, it feels plausible to me that this could be the case? I wonder what would might be a good approach to take to try to prove or disprove this?

If the clique-coclique bound does not hold for all walk-regular graphs in general, might it at least hold for e.g. all semi-symmetric graphs, in addition to the known families of walk-regular graphs that it holds for?

The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and coclique (independent set) numbers respectively.

It is known, in particular, that the clique-coclique bound holds for all vertex-transitive graphs and all distance-regular graphs - two families of walk-regular graphs.

The clique-coclique also appears to hold for all of the examples of walk-regular graphs that I know of that are neither vertex-transitive nor distance-regular  - which includes walk-regular graphs that are not semi-symmetric either.

Could it be possible that the clique-coclique bound actually holds for all (connected) walk-regular graphs?

By informal reasoning in head, it feels plausible to me that this could be the case? I wonder what would might be a good approach to take to try to prove or disprove this?

If the clique-coclique bound does not hold for all walk-regular graphs in general, might it at least hold for e.g. all semi-symmetric graphs, in addition to the known families of walk-regular graphs that it holds for?

The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and coclique (independent set) numbers respectively.

It is known, in particular, that the clique-coclique bound holds for all vertex-transitive graphs and distance-regular - two families of walk-regular graphs.

The clique-coclique also appears to hold for all of the examples of walk-regular graphs that I know of that are neither vertex-transitive nor distance-regular. It is also apparent that the clique-coclique bound holds for some other families of walk-regular graphs, namely semi-symmetric graphs.

Could it be possible that the clique-coclique bound actually holds for all (connected) walk-regular graphs?

By informal reasoning in head, it feels plausible to me that this could be the case? I wonder what would might be a good approach to take to try to prove or disprove this?

Source Link

Does the clique-coclique bound hold for all walk-regular graphs?

The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and coclique (independent set) numbers respectively.

It is known, in particular, that the clique-coclique bound holds for all vertex-transitive graphs and all distance-regular graphs - two families of walk-regular graphs.

The clique-coclique also appears to hold for all of the examples of walk-regular graphs that I know of that are neither vertex-transitive nor distance-regular - which includes walk-regular graphs that are not semi-symmetric either.

Could it be possible that the clique-coclique bound actually holds for all (connected) walk-regular graphs?

By informal reasoning in head, it feels plausible to me that this could be the case? I wonder what would might be a good approach to take to try to prove or disprove this?

If the clique-coclique bound does not hold for all walk-regular graphs in general, might it at least hold for e.g. all semi-symmetric graphs, in addition to the known families of walk-regular graphs that it holds for?