awarded
awarded
revised
Relationship between minimum vertex cover and matching width
deleted 4 characters in body
Loading…
awarded
Loading…
comment
Perfect matchings in certain classes of hypergraphs
I gave this answer mathoverflow.net/a/368902/17798 in a related question, but maybe it makes more sense to put it here as it generalizes the above example given by @Zur Luria
comment
making a random uniform hypergraph linear
See Theorem 3 and Lemma 4 here. A combinatorial classic - sparse graphs with high chromatic number Note that a 2-cycle is when two hyperedges intersect in at least 2 vertices. So by making the girth greater than $\ell$, this also ensures that the hypergraph is linear.
Loading…
comment
Does every primitive digraph have a directed cycle?
Does your definition of digraph allow for loops? If no loops are allowed, then yes. Since $(A^k)_{ii}$ is the number of walks of length $k$ from $v_i$ to $v_i$.
awarded
revised
Infinitely many counterexamples to Nash-Williams's conjecture about hamiltonicity?
Changed the title to make it a question. This makes my answer a response to a question rather than a refutation of a statement.
Loading…
comment
Infinitely many counterexamples to Nash-Williams's conjecture about hamiltonicity?
Again, my answer explains that these can’t be counterexamples. All of your examples are subgraphs of the non-Hamiltonian graph $K_{1,1,\dots,1,(n+1)/2}$. In this graph $d_{(n-1)/2}=(n-1)/2$ and $d_{(n+1)/2}=(n-1)/2$ so Nash-Williams doesn’t hold. Since you aren’t providing the degree sequence I can’t tell why you think it does.
Loading…
comment
Two more counterexamples to a conjecture from 1975 about hamiltonicity of digraphs
These two examples are closely related in the sense that g3 can be obtained from g2 by deleting the edge (5,4). One can verify that both of these satisfy the Nash-Williams condition and that g2 does not have a Hamiltonian cycle. Thus g3 does not have a Hamiltonian cycle. Since they are both planar, it would probably be helpful to draw them that way so the pictures can be read more clearly. I suggest redrawing the first picture with the vertices in three rows: 5 centered in the first row, 2,0,3,1 in the second row in that order, 4 centered on the bottom. Similarly with the second picture.
comment
A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?
@joro Yeah, they are definitely worth sharing. I guess it's up to you whether MO or arXiv is the correct venue. The thing I am most interested in is whether your other examples have a chance of generalizing to an infinite family of examples.
awarded
comment
comment
Graphs all of whose cuts are positive
This is almost obvious, but a necessary condition is that the sum of all the edge weights must be positive (since the sum of weights incident to every vertex must be positive).
awarded