Timeline for Lower bound on the individualization set for $k$-iso-regular graphs ( degree at max three )?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 20, 2017 at 15:40 | comment | added | Aaron Meyerowitz | A $k$-isoregular graph is also $2-$isoregular which means diameter $2$ and there are no vertices at distance $4$. Whatever you want to do for max degree 3, isoregular isn’t going to be relevant. | |
| Sep 19, 2017 at 16:43 | comment | added | Aaron Meyerowitz | 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 | |
| Sep 19, 2017 at 13:55 | comment | added | fddwd | Please provide a reference for the result ($\sqrt n \ log n$) (is it for at most degree 3 graphs ?) | |
| Sep 18, 2017 at 21:52 | comment | added | Aaron Meyerowitz | 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. | |
| Sep 17, 2017 at 20:57 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 86 characters in body; deleted 8 characters in body
|
| Sep 17, 2017 at 20:49 | comment | added | Aaron Meyerowitz | 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$. | |
| Sep 17, 2017 at 17:02 | comment | added | fddwd | I have seen this definition here.See page no-5 , second paragraph arxiv.org/pdf/1101.5211.pdf | |
| Sep 17, 2017 at 16:58 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |