## New answers tagged graph-theory

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 $...

- 34.7k

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 ...

- 19.8k

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)
...

- 155k

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 ...

- 34.7k

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

#### Related Tags

graph-theory × 4776co.combinatorics × 2018

graph-colorings × 484

reference-request × 414

algorithms × 321

pr.probability × 263

spectral-graph-theory × 243

random-graphs × 190

computational-complexity × 188

gr.group-theory × 186

extremal-graph-theory × 163

linear-algebra × 162

discrete-geometry × 158

mg.metric-geometry × 127

matching-theory × 116

combinatorial-optimization × 110

set-theory × 100

trees × 96

infinite-combinatorics × 92

matrices × 90

perfect-matchings × 90

hypergraph × 87

bipartite-graphs × 86

algebraic-graph-theory × 85

hamiltonian-graphs × 80