most recent 30 from http://mathoverflow.net 2013-05-20T06:25:16Z http://mathoverflow.net/feeds/user/7094 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian Esha 2010-11-08T06:52:00Z 2010-11-08T10:36:11Z

<p>Let us denote the edges incident on vertices of valence 2 as "required" as these edges has to be covered by a Hamiltonian circuit, if one exists on that (undirected) graph. Given a graph on which a proper subset of the "required" edges along with two edges incident on a vertex of valency $\geq 3$ form a cycle, can anything related to the Hamiltonicity of the graph be claimed? A few basic rules for the existence of Hamiltonian Cycles is listed here: <a href="http://www.mit.edu/~miforbes/ham_cycle.pdf" rel="nofollow">http://www.mit.edu/~miforbes/ham_cycle.pdf</a> Can rule (4) be extended in any way to answer this query?</p>

http://mathoverflow.net/questions/43641/graphs-having-unique-hamiltonian-paths-between-exactly-4-pair-of-vertices Esha 2010-10-26T07:47:33Z 2010-10-28T02:58:13Z

<p>Need some example graphs which are not hamiltonian, i.e, does not admit any hamiltonian cycle, but which have hamiltonian path. It has unique hamiltonian paths between exactly 4 pair of vertices. I have identified one such group of graphs. Would like to see more such examples. </p>

http://mathoverflow.net/questions/29578/monadic-second-order-mso-logic-on-graphs Esha 2010-06-26T05:51:13Z 2010-06-30T06:11:56Z

<p>Given a conflict graph G = (V, E), a man has to transport a set V of items/vertices across the river. Two items are connected by an edge in E, if they are conflicting and thus cannot be left alone together without human supervision. The available boat has capacity b ≥ 1, and thus can carry the man together with any subset of at most b items. A feasible schedule is a finite sequence of triples (L₁, B₁, R₁), (L₂, B₂, R₂), . . . , (L_s, B_s, R_s) of subsets of the item set V that satisfies the following conditions (FS1)–(FS3). The odd integer s is called the length of the schedule.</p> <p>(FS1) For every k, the sets L_k, B_k, R_k form a partition of V . The sets L_k and R_k form stable sets in G. The set B_k contains at most b elements.</p> <p>(FS2) The sequence starts with L₁ ∪ B₁ = V and R₁ = ∅, and the sequence ends with L_s = ∅ and B_s ∪ R_s = V .</p> <p>(FS3) For even k ≥ 2, we have B_k ∪ R_k = B_k-1 ∪ R_k-1 and L_k = L_k-1. For odd k ≥ 3, we have L_k ∪ B_k = L_k-1 ∪ B_k-1 and R_k = R_k-1.</p> <p>Known Result: VertexCover(G) ≤ b ≤ VertexCover(G)+1.</p> <p>Please help formulate this problem in MSO. </p>

http://mathoverflow.net/questions/29578/monadic-second-order-mso-logic-on-graphs/29793#29793 Esha 2010-06-28T14:03:39Z 2010-06-28T14:03:39Z

<p>I am not sure whether it is definitely expressible in MSO or not. </p>

http://mathoverflow.net/questions/29578/monadic-second-order-mso-logic-on-graphs/29617#29617 Esha 2010-06-26T14:44:15Z 2010-06-26T14:44:15Z

<p>This is not a homework problem.. This problem is NP-hard on general graphs. But has polynomial time solution for some special classes. Just like the classic Gupta-Vizing's theorem of Graph coloring, where number of colors required is either D (highest degree) or D+1, but still the problem is NP-Complete. This is in fact a generalization of the River crossing problem, which appeared in "Propositiones ad acuendos iuvenes” </p>

http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian Esha 2010-11-09T02:25:29Z 2010-11-09T02:25:29Z

cstheory.stackexchange link: <a href="http://cstheory.stackexchange.com/questions/2777/necessary-condition-for-a-graph-to-be-non-hamiltonian" rel="nofollow" title="necessary condition for a graph to be non hamiltonian">cstheory.stackexchange.com/questions/2777/&hellip;</a>

http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian Esha 2010-11-08T13:34:44Z 2010-11-08T13:34:44Z

@ Tsuyoshi Ito: Is crossposting not allowed?

http://mathoverflow.net/questions/45272/necessary-condition-for-a-graph-to-be-non-hamiltonian Esha 2010-11-08T10:34:34Z 2010-11-08T10:34:34Z

Sorry.. the cycle is formed by all &quot;required&quot; edges except two. These two are the two edges incident to a vertex of valence $\geq 3$.

http://mathoverflow.net/questions/43641/graphs-having-unique-hamiltonian-paths-between-exactly-4-pair-of-vertices/43784#43784 Esha 2010-10-28T02:59:59Z 2010-10-28T02:59:59Z

Sorry, forgot to mention. It has to have unique hamiltonian paths between exactly 4 pair of vertices. Also, tthe triangles can be generalized as $C_m$ for some $m$

http://mathoverflow.net/questions/43641/graphs-having-unique-hamiltonian-paths-between-exactly-4-pair-of-vertices Esha 2010-10-27T04:50:29Z 2010-10-27T04:50:29Z

The first one is not only for triangles, it actually generalizes to a family of graphs and that is exactly the class I have in mind. I would like to see more such &quot;graph families&quot;.. preferably construction to generate this kind of graphs. About your next example, I am not very clear. How can you attach a clique at some point on the path between the two triangles? that will form a local loop instead of beoing covered by HP.

http://mathoverflow.net/questions/29578/monadic-second-order-mso-logic-on-graphs Esha 2010-07-17T07:02:47Z 2010-07-17T07:02:47Z

Even CMSO is fine as CMSO logic is provably a strict extension of MSO logic, since it is not definable in pure MSO for arbitrary structures. But nevertheless CMSO-problems for structures of bounded tree-width can be reduced to MSO-problems for binary trees since CMSO logic is definable in MSO logic for binary trees.

http://mathoverflow.net/questions/29578/monadic-second-order-mso-logic-on-graphs/29918#29918 Esha 2010-07-17T06:58:00Z 2010-07-17T06:58:00Z

Even CMSO is fine.

http://mathoverflow.net/questions/29578/monadic-second-order-mso-logic-on-graphs/29886#29886 Esha 2010-07-16T06:30:19Z 2010-07-16T06:30:19Z

Yes, I precisely want to express that for any given graph there is a feasible schedule, either with b=VertexCover(G) or b=VertexCover(G)+1.

http://mathoverflow.net/questions/29578/monadic-second-order-mso-logic-on-graphs/29918#29918 Esha 2010-06-29T15:46:09Z 2010-06-29T15:46:09Z

Thanks a lot. Yes, there is an upperbound on the number of rounds,n = stability number of the graph.

http://mathoverflow.net/questions/29578/monadic-second-order-mso-logic-on-graphs/29874#29874 Esha 2010-06-29T11:55:32Z 2010-06-29T11:55:32Z

This is the generalized Alcuin Number problem..