Skip to main content
MathOverflow

Return to Question

Clarified the definition of the graph.
Source Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Calculation independent What is the independence number of a specialthis graph which is a generalization of a Kneser graph?

Can some one calculate the independent number of the following graph:

Suppose the setLet $\mathfrak{A}=\{1,2,\dots,8\}$ and considerconstruct a graph as follows. Let the vertexvertices of the graph isbe the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ andare distinct and between two vertex. Two vertices $B=(\{a,b,c\},\{d,e\})$$(\{a,b,c\},\{d,e\})$ and $C=(\{f,g,h\},\{k,l\})$ is an edge$(\{f,g,h\},\{k,l\})$ are adjacent if $B\cap C=\{a,b,c\}=\{f,g,h\}$ $\{a,b,c\}=\{f,g,h\}$ and $\{a,b,c,d,e\} \cap \{f,g,h,k,l\}=\{a,b,c\}$ or if $B\cap C=\{d,e\}=\{k,l\}$$\{d,e\}=\{k,l\}$ and $\{a,b,c,d,e\} \cap \{f,g,h,k,l\}=\{d,e\}$.

My question is what is the independentindependence number of this graph?

Recall that the independentindependence number of a graph is the maximalmaximum number of vertices with no edge between them.

Calculation independent number of a special graph which is a generalization of Kneser graph

Can some one calculate the independent number of the following graph:

Suppose the set $\mathfrak{A}=\{1,2,\dots,8\}$ and consider the vertex of graph is the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ and distinct and between two vertex $B=(\{a,b,c\},\{d,e\})$ and $C=(\{f,g,h\},\{k,l\})$ is an edge if $B\cap C=\{a,b,c\}=\{f,g,h\}$ or $B\cap C=\{d,e\}=\{k,l\}$.

My question is what is the independent number of this graph?

Recall that the independent number of a graph is the maximal number of vertices with no edge between them.

What is the independence number of this graph which is a generalization of a Kneser graph?

Let $\mathfrak{A}=\{1,2,\dots,8\}$ and construct a graph as follows. Let the vertices of the graph be the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ are distinct. Two vertices $(\{a,b,c\},\{d,e\})$ and $(\{f,g,h\},\{k,l\})$ are adjacent if $\{a,b,c\}=\{f,g,h\}$ and $\{a,b,c,d,e\} \cap \{f,g,h,k,l\}=\{a,b,c\}$ or if $\{d,e\}=\{k,l\}$ and $\{a,b,c,d,e\} \cap \{f,g,h,k,l\}=\{d,e\}$.

My question is what is the independence number of this graph?

Recall that the independence number of a graph is the maximum number of vertices with no edge between them.

deleted 3 characters in body
Source Link
Maryam
Maryam
  • 147
  • 3

Can some one calculate the independent number of the following graph:

Suppose the set $\mathfrak{A}=\{1,2,\dots,8\}$ and consider the vertex of graph is the set of all $A=\{a,b,c\}\cup\{d,e\}$$A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ and distinct and between two vertex $B=\{a,b,c\}\cup\{d,e\}$$B=(\{a,b,c\},\{d,e\})$ and $C=\{f,g,h\}\cup\{k,l\}$$C=(\{f,g,h\},\{k,l\})$ is an edge if $B\cap C=\{a,b,c\}=\{f,g,h\}$ or $B\cap C=\{d,e\}=\{k,l\}$.

My question is what is the independent number of this graph?

Recall that the independent number of a graph is the maximal number of vertices with no edge between them.

Can some one calculate the independent number of the following graph:

Suppose the set $\mathfrak{A}=\{1,2,\dots,8\}$ and consider the vertex of graph is the set of all $A=\{a,b,c\}\cup\{d,e\}$ where $a,b,c,d,e\in \mathfrak{A}$ and distinct and between two vertex $B=\{a,b,c\}\cup\{d,e\}$ and $C=\{f,g,h\}\cup\{k,l\}$ is an edge if $B\cap C=\{a,b,c\}=\{f,g,h\}$ or $B\cap C=\{d,e\}=\{k,l\}$.

My question is what is the independent number of this graph?

Recall that the independent number of a graph is the maximal number of vertices with no edge between them.

Can some one calculate the independent number of the following graph:

Suppose the set $\mathfrak{A}=\{1,2,\dots,8\}$ and consider the vertex of graph is the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ and distinct and between two vertex $B=(\{a,b,c\},\{d,e\})$ and $C=(\{f,g,h\},\{k,l\})$ is an edge if $B\cap C=\{a,b,c\}=\{f,g,h\}$ or $B\cap C=\{d,e\}=\{k,l\}$.

My question is what is the independent number of this graph?

Recall that the independent number of a graph is the maximal number of vertices with no edge between them.

added 25 characters in body; edited tags; edited title
Source Link
user9072
user9072

Calculation independent number of a special graph which is a generalization of Kneser graph$$graph

Can some one calculate the independent number of the following graph:

Suppose the set $\mathfrak{A}=\{1,2,\dots,8\}$ and consider the vertex of graph is the set of all $A=\{a,b,c\}\cup\{d,e\}$ where $a,b,c,d,e\in \mathfrak{A}$ and distinct and between two vertex $B=\{a,b,c\}\cup\{d,e\}$ and $C=\{f,g,h\}\cup\{k,l\}$ is an edge if $B\cap C=\{a,b,c\}=\{f,g,h\}$ or $B\cap C=\{d,e\}=\{k,l\}$. My

My question is aboutwhat is the independent number of this graph?

IndependentRecall that the independent number of a graph is the maximal sizenumber of verteicesvertices with no edge between them.

Calculation independent number of a special graph which is a generalization of Kneser graph$$

Can some one calculate the independent number of the following graph:

Suppose the set $\mathfrak{A}=\{1,2,\dots,8\}$ and consider the vertex of graph is the set of all $A=\{a,b,c\}\cup\{d,e\}$ where $a,b,c,d,e\in \mathfrak{A}$ and distinct and between two vertex $B=\{a,b,c\}\cup\{d,e\}$ and $C=\{f,g,h\}\cup\{k,l\}$ is an edge if $B\cap C=\{a,b,c\}=\{f,g,h\}$ or $B\cap C=\{d,e\}=\{k,l\}$. My question is about the independent number of this graph?

Independent number of a graph is maximal size of verteices with no edge between them.

Calculation independent number of a special graph which is a generalization of Kneser graph

Can some one calculate the independent number of the following graph:

Suppose the set $\mathfrak{A}=\{1,2,\dots,8\}$ and consider the vertex of graph is the set of all $A=\{a,b,c\}\cup\{d,e\}$ where $a,b,c,d,e\in \mathfrak{A}$ and distinct and between two vertex $B=\{a,b,c\}\cup\{d,e\}$ and $C=\{f,g,h\}\cup\{k,l\}$ is an edge if $B\cap C=\{a,b,c\}=\{f,g,h\}$ or $B\cap C=\{d,e\}=\{k,l\}$.

My question is what is the independent number of this graph?

Recall that the independent number of a graph is the maximal number of vertices with no edge between them.

added 18 characters in body
Source Link
Maryam
Maryam
  • 147
  • 3
added 97 characters in body; edited title
Source Link
Maryam
Maryam
  • 147
  • 3
Source Link
Maryam
Maryam
  • 147
  • 3