# Lower bound on the individualization set for $k$-iso-regular graphs ( degree at max three )?

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.

• How is the number of neighbours of a $k$-tuple defined? – Brendan McKay Sep 17 '17 at 10:35
• @ Brendan McKay It is not just number of neighbours, but number of common neighbours. I have edited the question – fddwd Sep 17 '17 at 12:15
• The example seems to be 1-iso-regular but not 2-iso-regular. Otherwise I don't understand the definition. Please give a non-trivial example of a 2-iso-regular graph with maximum degree 3. Frankly I am doubting their existence (except for some tiny graphs). – Brendan McKay Sep 17 '17 at 13:17
• @ Brendan McKay This is 4-iso-regular – fddwd Sep 17 '17 at 13:29
• I down-voted. Several days after Aaron told your that your definition of $k$-iso-regular makes no sense, you still didn't fix it. Under your definition, every graph is $k$-iso-regular when $k$ is greater than the maximum degree, and it is not true that $k$-iso-regular implies $k-1$-iso-regular. I'll also note that the definition in Douglas' paper is different from the definition in his reference  that he claims to get it from. – Brendan McKay Sep 21 '17 at 8:56

If you are looking for results in the literature you need to be sure you are using a definition that others use. Do you have a reference for your definition of $k$-iso-regular? The definition I am familiar with is that for any set of up to $k$ vertices the number of common neighbors depends only on the isomorphism type of the induced graph on those vertices so:
Every vertex has the same number of neighbors (aka regular) AND the number of common neighbors of two vertices $u,v$ depends only if $uv$ is or is not an edge (aka strongly regular) AND the number of common neighbors of $u,v,w$ depends on the isomorphism type ($4$ cases) of the induced graph on $u,v,w$ etc up to $k$ vertex sets.
• That definition says every $k$-element set of a certain isomorphism type . Although they don't say it explicitly, it is also clear that the condition applies to sets of size up to $k$ since it says $5$-iso-regular implies $t$-iso-regular$for all$t$. – Aaron Meyerowitz Sep 17 '17 at 20:49 • OK but your graph above is not$2$-isoregular so also not$k$-isoregular for$k=3,4.$I'm sure that constant size would not be enough. In the event that the graphs are$2$-isoregular (hence diameter$2$) it is known that$\sqrt{n}\log{n}$vertices suffice. If a constant size was possible in general that wouldn't be a very good result. – Aaron Meyerowitz Sep 18 '17 at 21:52 • Please provide a reference for the result ($\sqrt n \ log n\$) (is it for at most degree 3 graphs ?) – fddwd Sep 19 '17 at 13:55