Return to Question

Assume graphs of degree at most three for this question.

$k$-iso-regular graphs are the graphs in which every $k$-tuple has a same number of common neighbors. The $k$-dimensional Weisfeiler Lehman fails on $k$-iso-regular regular graphs. $k$ is a constant here, definitely if $k = O(n)$ then $k$-dimensional Weisfeiler Lehman will work correctly.

Suppose I bound the maximum degree of the input graph to three, then also there are graphs on which $k$-dimensional Weisfeiler Lehman fails. So one possible way to deal this situation is individualization along with $k$-dimensional Weisfeiler Lehman.

Small example of an iso-regular graph:

Question : Is there any known claim on the size of individualization set for $k$-iso-regular graphs ( degree at max three )? Is constant size individualization set possible? I tried to search on google scholar, but did not get anything specific.

Assume graphs of degree at most three for this question.

A graph is said to be k-isoregular if for every subset $S$ of at most $k$ vertices the number common neighbors of the elements of $S$ depends only on the isomorphism type of the subgraph induced by $S$. The $k$-dimensional Weisfeiler Lehman fails on $k$-iso-regular regular graphs. $k$ is a constant here, definitely if $k = O(n)$ then $k$-dimensional Weisfeiler Lehman will work correctly.

Suppose I bound the maximum degree of the input graph to three, then also there are graphs on which $k$-dimensional Weisfeiler Lehman fails. So one possible way to deal this situation is individualization along with $k$-dimensional Weisfeiler Lehman.

Small example of an iso-regular graph:

Question : Is there any known claim on the size of individualization set for $k$-iso-regular graphs ( degree at max three )? Is constant size individualization set possible? I tried to search on google scholar, but did not get anything specific.

Assume graphs of degree at most three for this question.

$k$-iso-regular graphs are the graphs in which every $k$-tuple has a same number of common neighbors. The $k$-dimensional Weisfeiler Lehman fails on $k$-iso-regular regular graphs. $k$ is a constant here, definitely if $k = O(n)$ then $k$-dimensional Weisfeiler Lehman will work correctly.

Suppose I bound the maximum degree of the input graph to three, then also there are graphs on which $k$-dimensional Weisfeiler Lehman fails. So one possible way to deal this situation is individualization along with $k$-dimensional Weisfeiler Lehman.

Small example of an iso-regular graph:

Question : Is there any known claim on the size of individualization set for $k$-iso-regular graphs ( degree at max three )? Is constant size individualization set possible? I tried to search on google scholar, but did not get anything specific.

Assume graphs of degree at most three for this question.

$k$-iso-regular graphs are the graphs in which every $k$-tuple has a same number of common neighbors. The $k$-dimensional Weisfeiler Lehman fails on $k$-iso-regular regular graphs. $k$ is a constant here, definitely if $k = O(n)$ then $k$-dimensional Weisfeiler Lehman will work correctly.

Suppose I bound the maximum degree of the input graph to three, then also there are graphs on which $k$-dimensional Weisfeiler Lehman fails. So one possible way to deal this situation is individualization along with $k$-dimensional Weisfeiler Lehman.

Small example of an iso-regular graph:

Question : Is there any known claim on the size of individualization set for $k$-iso-regular graphs ( degree at max three )? Is constant size individualization set possible? I tried to search on google scholar, but did not get anything specific.

Assume graphs of degree at most three for this question.

$k$-iso-regular graphs are the graphs in which every $k$-tuple has a same number of common neighbors. The $k$-dimensional Weisfeiler Lehman fails on $k$-iso-regular regular graphs. $k$ is a constant here, definitely if $k = O(n)$ then $k$-dimensional Weisfeiler Lehman will work correctly.

Suppose I bound the maximum degree of the input graph to three, then also there are graphs on which $k$-dimensional Weisfeiler Lehman fails. So one possible way to deal this situation is individualization along with $k$-dimensional Weisfeiler Lehman.

Small example of an iso-regular graph:

Question : Is there any known claim on the size of individualization set for $k$-iso-regular graphs ( degree at max three )? Is constant size individualization set possible? It should be possible because I am here talking about graphs of degree at most three and there is an already polynomial time algorithm for bounded degree graph by E.M Luks.

I tried to search on google scholar, but did not get anything specific.

Assume graphs of degree at most three for this question.

$k$-iso-regular graphs are the graphs in which every $k$-tuple has a same number of common neighbors. The $k$-dimensional Weisfeiler Lehman fails on $k$-iso-regular regular graphs. $k$ is a constant here, definitely if $k = O(n)$ then $k$-dimensional Weisfeiler Lehman will work correctly.

Suppose I bound the maximum degree of the input graph to three, then also there are graphs on which $k$-dimensional Weisfeiler Lehman fails. So one possible way to deal this situation is individualization along with $k$-dimensional Weisfeiler Lehman.

Small example of an iso-regular graph:

Question : Is there any known claim on the size of individualization set for $k$-iso-regular graphs ( degree at max three )? Is constant size individualization set possible? I tried to search on google scholar, but did not get anything specific.