Timeline for Importance of the $2^{\tau(G)}\leqslant A(n,g(G))$ conjecture
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2018 at 11:12 | answer | added | Peter Heinig | timeline score: 1 | |
| Feb 27, 2018 at 6:28 | comment | added | Peter Heinig | Graphs Comb. 19, No. 4, 547-550 (2003)], wherein a proof is given that if $Q_n$ is the $n$-dimensional hypercube, then $2^{n-1}-\tau(Q_n) = A(n,g(Q_n))$ if and only if $Q_n$ contains a minimum feedback set which moreover happens to be an independent set. I'm cognizant of this being merely roughly similar to the conjecture in the OP. Second, [Mieczysław Borowiecki, Ewa Drgas-Burchardt, Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs, Discrete Math. 312, No. 14, 2146-2152 (2012)], in its last section has a few relevant remarks. | |
| Feb 27, 2018 at 6:17 | comment | added | Peter Heinig | @potato: it makes a little more sense; personally, I still don't understand what "graphs describing $A(n,d)$" is supposed to mean. Also, each of the three questions in the OP seems rather vague to me: 'is this an attempt?', 'are there consequences?', 'does G being directed matter?' I do not mean to be flippant, but strictly speaking the answer is three times 'obviously yes'. That being said, let me add that the most relevant publications I know (though still only trangentially so; in particular they are about undirected graphs) are: [D. A. Pike, Decycling hypercubes, ... | |
| Feb 26, 2018 at 22:19 | comment | added | potato | @PeterHeinig : does it make more sense now ? | |
| Feb 26, 2018 at 22:18 | history | edited | potato | CC BY-SA 3.0 |
added 185 characters in body
|
| Feb 26, 2018 at 21:43 | comment | added | potato | @bof: It should be fixed now (I just transcribed one-to-one the paper we got). PeterHeinig: thanks ! | |
| Feb 26, 2018 at 21:42 | history | edited | potato | CC BY-SA 3.0 |
added 22 characters in body
|
| Feb 26, 2018 at 18:48 | comment | added | Peter Heinig | @bof: while you are right that this is not defined, it is clear from context that $I\subseteq V(G)$ and that $n=\lvert V(G)\rvert$. at potato: your mentioning 'codes' is indeed relevant, since e.g. according to [C. Godsil, Algebraic Combinatorics, CRC Press, 1993, ISBN 9780412041310; p. 205], the function $A(n,d)$ is the maximum cardinality of a code of minimum distance $d$ inside the $n$-dimensional hypercube. | |
| Feb 26, 2018 at 17:39 | comment | added | bof | "subset $I$" of what? $V(G)$ or $E(G)$ "If $G$ is acyclic, let $g(G)=n+1$" where $n$ is what? | |
| Feb 26, 2018 at 17:06 | review | First posts | |||
| Feb 26, 2018 at 17:20 | |||||
| Feb 26, 2018 at 17:04 | history | asked | potato | CC BY-SA 3.0 |