$G$ is an $(x,y)$-graph if $x>C(G)$ and $y>I(G)$

28 Views Asked by At

I dont understand this definition, I'm new in this topic.

Definition 1: $I(G)$, the independence number of the graph $G$, is the maximum number of point of $G$ thath can be chosen so that no two are joined by an edge.

Definition 2: $C(G)$, the clique number of the graph $G$, is the maximum number of point in any complete subgraph of $G$.

I understand the definition 1 and 2, then I am not understanding.>..

Definition 3: $G$ is an $(x,y)$-graph if $x>C(G)$ and $y>I(G)$

could you give me an example to understand, please?

1

There are 1 best solutions below

0
On

The following graph is $(4,4)$ I think as the max clique subgraph is $K_3$ and $I(G)=3$. It is also $(n,m)$ for $n\geq4 ,m \geq 4$.

enter image description here

And this one is $(5,5)$ as $C(G)=4$ and $I(G)=4$. It is also $(n,m)$ for $n\geq5 ,m \geq 5$ enter image description here