Skip to main content
edited tags
Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
[Edit removed during grace period]
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
deleted 72 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

LetDo there exist a family of graphs with the property: $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes \bar{G}}}\right)\right| = O(\log(N_{G}))$$ where $G$ be ais the graph and, $\bar{G}$ is its complement. Let, $\boxtimes$ denotedenotes the strong product. Let, $\alpha(G)$ denotedenotes the independence number of $G$ and $N_{G}$ beis the number of vertices of $G$.

Is $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes \bar{G}}}\right)\right| = O(\log(N_{G}))?$$

Do self-complementary graphs satisfy this property?

Atleast is there a family of graphs that satisfy this property?

Let $G$ be a graph and $\bar{G}$ its complement. Let $\boxtimes$ denote strong product. Let $\alpha(G)$ denote independence number of $G$ and $N_{G}$ be the number of vertices of $G$.

Is $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes \bar{G}}}\right)\right| = O(\log(N_{G}))?$$

Do self-complementary graphs satisfy this property?

Atleast is there a family of graphs that satisfy this property?

Do there exist a family of graphs with the property: $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes \bar{G}}}\right)\right| = O(\log(N_{G}))$$ where $G$ is the graph, $\bar{G}$ is its complement, $\boxtimes$ denotes the strong product, $\alpha(G)$ denotes the independence number of $G$ and $N_{G}$ is the number of vertices of $G$?

Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading