New answers tagged

1 vote
Accepted

Graphs with $n$ vertices and $m$ edges and more probable property

There is a $C_4$-free bipartite graph $B$ with 19 vertices on one side, 20 vertices on the other side, and 92 edges. Its vertices have degree 4 or 5, so it is easy to find a path $P$ of 21 edges in $...
4 votes

Does $\{0,1\}^{<\omega}$ have a Hamiltonian path?

Let $B_k$ be the subset of $\{0,1\}^{<\omega}$ whose support is contained in $[k]$. It is clear that the induced subgraph on $B_k$ is isomorphic to the graph of the $k$-dimensional hypercube. It is ...
  • 1,771
7 votes
Accepted

Does $\{0,1\}^{<\omega}$ have a Hamiltonian path?

I'm going to write $\mathcal{S}$ for what you call $\{0,1\}^{<\omega}$, since I'm used to the latter referring to the set of finite binary strings. Yes, and moreover there is a relatively simple ...
2 votes
Accepted

Is there a monograph or review of Hamiltonian cycles of graphs (or long cycles of graphs)?

Q: Is there a monograph (or review) of Hamiltonian cycles of graphs (or long cycles of graphs)? One possible answer (from a specific perspective) is Hamiltonian Cycle Problem and Markov Chains (2012) ...
3 votes
Accepted

Do all graphs with $n$ vertices and $m$ edges have a special property?

For $n=53$ and $m=113$, you can't even get close in general. Take 7 copies of $K_5$ and 3 copies of $K_6$, all disjoint. Remove any two edges; now you have 53 vertices and 113 edges. No complete ...
1 vote

Do all graphs with $n$ vertices and $m$ edges have a special property?

Let $\psi(n)\approx\sqrt{n}$ denote the positive solution to $x^2+2x=n$. Note that if $|V_1||V_2|+|V_1|+|V_2|>n$, then either $|V_1|\geq \psi(n)$ or $|V_2|\geq \psi(n)$. This implies that all ...
  • 11
0 votes

Vertex degree on random graphs

Just an amateur answer, I would assume there's a paper or known approach out there from experts. I would partition the vertices into equal sets $U,V$ and delete edges to make it a bipartite graph. It ...
  • 3,963
1 vote
Accepted

Eigenvalues of directed graph with one outward edge for each vertex

Here is an alternative (more combinatorial) proof to the one linked to in my comment. Suppose that the digraph $D$ has a vertex of in-degree zero, which we may assume is vertex $1$. Then letting $\...
  • 11.3k
3 votes

Quasi-random vs pseudo-random graphs

Someone else will probably have a better answer, but I can't leave a comment. In my experience "quasi-random graph" (almost?) always refers to the Chung Graham Wilson type graphs you ...
  • 76
1 vote
Accepted

Algorithm for finding a minimum weight circuit in a weighted binary matroid

The problem is NP-hard (even in the unweighted case) via a well-known connection to coding theory. Namely, if $A$ is the parity check matrix of a binary linear code $C$, then the distance of $C$ is ...
  • 29.2k
2 votes
Accepted

Expected doubling constant of a random Erdős–Rényi graph

Let me assume $p > (1 + \varepsilon)(2 \ln n/ n)^{1/2}$, this in particular includes the case of constant $p \in (0,1)$. If $p > (1 + \varepsilon)(2 \ln n/ n)^{1/2}$ then w.h.p. the binomial ...
  • 371

Top 50 recent answers are included