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:

enter image description here

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.

  • $\begingroup$ How is the number of neighbours of a $k$-tuple defined? $\endgroup$ – Brendan McKay Sep 17 '17 at 10:35
  • $\begingroup$ @ Brendan McKay It is not just number of neighbours, but number of common neighbours. I have edited the question $\endgroup$ – fddwd Sep 17 '17 at 12:15
  • $\begingroup$ 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). $\endgroup$ – Brendan McKay Sep 17 '17 at 13:17
  • $\begingroup$ @ Brendan McKay This is 4-iso-regular $\endgroup$ – fddwd Sep 17 '17 at 13:29
  • $\begingroup$ 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 [11] that he claims to get it from. $\endgroup$ – 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.

also For graphs of bounded degree ,GI is decidable in polynomial time.

| cite | improve this answer | |
  • $\begingroup$ I have seen this definition here.See page no-5 , second paragraph arxiv.org/pdf/1101.5211.pdf $\endgroup$ – fddwd Sep 17 '17 at 17:02
  • 1
    $\begingroup$ 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$. $\endgroup$ – Aaron Meyerowitz Sep 17 '17 at 20:49
  • $\begingroup$ 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. $\endgroup$ – Aaron Meyerowitz Sep 18 '17 at 21:52
  • $\begingroup$ Please provide a reference for the result ($\sqrt n \ log n$) (is it for at most degree 3 graphs ?) $\endgroup$ – fddwd Sep 19 '17 at 13:55
  • $\begingroup$ My starting point was that your definition of isoregular was not useful for the question. I would look at this article and papers which reference it for more helpful information and bounds people.cs.uchicago.edu/~laci/papers/13focs-SRG.pdf $\endgroup$ – Aaron Meyerowitz Sep 19 '17 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.