3
$\begingroup$

Given two graphs $G,H$ is there a product $\star$ such that 1. and 2. holds where $\alpha$ refers to independence number?

  1. $$\alpha(G\star H)=\alpha(G)\alpha(H)=\alpha(H\star G)$$

  2. $$G\star H\cong H\star G$$

Lexicographic product satisfies 1. but not 2.

Also other than Lexicographic product is there any other product that satisfies 1.?

$\endgroup$
1
  • 6
    $\begingroup$ What sort of "product" are you looking for? You can obviously construct binary operations with these properties (but this completely artificial), e.g. by defining G*H = α(G)α(H)K₁. I know of no "common" graph product that satisfies both 1. and 2. $\endgroup$ Commented Mar 19, 2017 at 12:00

1 Answer 1

3
$\begingroup$

The "disjunctive" or "OR" product works (see https://en.wikipedia.org/wiki/Graph_product). For graphs $G$ and $H$, define $G * H$ as the graph with vertex set $V(G) \times V(H)$, with two vertices $(g,h)$ and $(g',h')$ being adjacent if $g \sim g'$ or $h \sim h'$, where $\sim$ denotes adjacency. Obviously $G * H \cong H * G$. It is also easy to see that if $S_G$ and $S_H$ are independent sets in $G$ and $H$, then $S_G \times S_H$ is an independent set in $G * H$, and thus $\alpha(G * H) \ge \alpha(G)\alpha(H)$. Conversely, if $S$ is an independent set in $G * H$, then define the sets \begin{align*} S_G &= \{g : \exists h \in V(H) \text{ s.t. } (g,h) \in S\}; \\ S_H &= \{h : \exists g \in V(G) \text{ s.t. } (g,h) \in S\}. \end{align*} These are just the "projections" of $S$ onto $G$ and $H$ respectively. By the definition of $G * H$ and the fact that $S$ is an independent set, we have that $S_G$ and $S_H$ are independent sets in $G$ and $H$ respectively. Also, $S \subseteq S_G \times S_H$, and thus $\alpha(G * H) \le \alpha(G)\alpha(H)$ as desired.

Note that this is related to the so-called "strong" product, denoted by $\boxtimes$, by the equation $G * H = \overline{\overline{G} \boxtimes \overline{H}}$. The lexicographic product is a subgraph of the disjunctive product.

$\endgroup$
0

You must log in to answer this question.

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