0
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ How is the number of neighbours of a $k$-tuple defined? $\endgroup$
    – Brendan McKay
    Commented Sep 17, 2017 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
    Commented Sep 17, 2017 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
    Commented Sep 17, 2017 at 13:17
  • $\begingroup$ @ Brendan McKay This is 4-iso-regular $\endgroup$
    – fddwd
    Commented Sep 17, 2017 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
    Commented Sep 21, 2017 at 8:56

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I have seen this definition here.See page no-5 , second paragraph arxiv.org/pdf/1101.5211.pdf $\endgroup$
    – fddwd
    Commented Sep 17, 2017 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
    Commented Sep 17, 2017 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
    Commented Sep 18, 2017 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
    Commented Sep 19, 2017 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
    Commented Sep 19, 2017 at 16:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .