Timeline for Determinants in Graph Theory
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 2, 2017 at 15:38 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
This edit is to second the recent correction of Tyler Streeter. To give context and support, I added a relevant part of Biggs, Algebraic Graph Theory, CUP, second edition.
|
| Sep 2, 2017 at 15:25 | review | Suggested edits | |||
| S Sep 2, 2017 at 15:38 | |||||
| S Sep 2, 2017 at 14:50 | history | suggested | Tyler Streeter | CC BY-SA 3.0 |
$r(G)$ definition is incorrect: it should also include $K_2$ components. See e.g. [Harary, 1962](http://yaroslavvb.com/papers/harary-determinant.pdf) eq.8, where $e_i$ (same as $r(G)$ here) is defined at the bottom of p.207 as the number of even components that are lines ($K_2$) or cycles.
|
| Sep 2, 2017 at 12:35 | review | Suggested edits | |||
| S Sep 2, 2017 at 14:50 | |||||
| Mar 24, 2016 at 3:21 | comment | added | Tyler Streeter | I'll think about special cases where all even components are $K_2$. In any case, thanks for the quick responses, and for posting this helpful answer in the first place. | |
| Mar 23, 2016 at 23:48 | history | edited | Jernej | CC BY-SA 3.0 |
added 6 characters in body
|
| Mar 23, 2016 at 23:48 | comment | added | Jernej | @TylerStreeter Yes, you're right about the references. I am not sure at this point how I got to the presented definition of $r(H)$ and at this point its safer to just edit the post to use the number of even cycles. | |
| Mar 23, 2016 at 22:28 | comment | added | Tyler Streeter | To rephrase my comments: in both the Biggs and Harary references, it appears that the expression involves $(-1)$ raised to the power "number of even components," not "number of $K_2$ components." So the description above appears incorrect, unless I'm missing something. | |
| Mar 23, 2016 at 21:10 | comment | added | Tyler Streeter | Even in this specific class of graphs (i.e. spanning subgraphs of $G$ having only $K_2$ and cycles as components), I think $r(H)$ here should be (congruent to, mod 2) the number of even components, not the number of $K_2$ components. Or am I missing something? | |
| Mar 23, 2016 at 20:25 | comment | added | Jernej | @TylerStreeter That's right r(H) has a different meaning in general (the rank of H). In this case the function is simplified since we only evaluate it for the specific class of graphs | |
| Mar 23, 2016 at 20:20 | comment | added | Tyler Streeter | Looking at Biggs (chapter "Determinant expansions"), and also the original Harary 1962 paper referenced there, it seems that $r(H)$ represents the number of even components, not the number of $K_2$ components as you describe here. Is that correct? | |
| S Jul 17, 2014 at 19:33 | history | suggested | Jeroen Zuiddam | CC BY-SA 3.0 |
There were two dots after K_2.
|
| Jul 17, 2014 at 19:26 | review | Suggested edits | |||
| S Jul 17, 2014 at 19:33 | |||||
| Jun 27, 2013 at 10:16 | history | edited | Jernej | CC BY-SA 3.0 |
added 6 characters in body
|
| Jun 27, 2013 at 9:12 | history | answered | Jernej | CC BY-SA 3.0 |