**0**

votes

**1**answer

257 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**7**

votes

**1**answer

450 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...

**3**

votes

**1**answer

81 views

### Bounds for number of edges of a graph, given girth and number of vertices

In reading a paper, I came across an affirmation
"a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges"
In a previous question I asked in this site about it, I was reffered to a ...

**0**

votes

**1**answer

53 views

### Looking for source: Max num of edges of graph with given number of vertices and given girth

In a paper I am reading, the author states:
"It is simple and well known that a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges"
He says that a proof can be found on Extremal ...

**10**

votes

**0**answers

116 views

### Asymptotics of subgraph densities in graphons

In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...

**0**

votes

**0**answers

26 views

### Possible Number of Repetation of a Submatrix

Notation:
$H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...

**4**

votes

**1**answer

163 views

### What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?

Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...

**0**

votes

**1**answer

64 views

### Reference for Turan Density

I am working a 3-graph problem. I convert it to calculate Turan density, that is $lim_{n\to \infty}\frac{ex_3(n,F)}{\binom{n}{3}}$, where F is a3-graph. I'd like to know are there some methods and ...

**1**

vote

**0**answers

80 views

### maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...

**0**

votes

**0**answers

59 views

### Tight bound of Turan number for K_{1,t,t}?

I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t.
The motivation is that we now $ex_2(n,K_{t,t})=O(n^...

**17**

votes

**2**answers

974 views

### Determine or estimate the number of maximal triangle-free graphs on $n$ vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
http://www.math.ucsd.edu/~erdosproblems/erdos/...

**0**

votes

**1**answer

83 views

### Vertex cover of regular graph

(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on ...

**2**

votes

**1**answer

143 views

### Extremal combinatorics on bipartite graphs

One open question in extremal graph Theory is the so-called Zarankiewicz problem
(see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed ...

**5**

votes

**2**answers

1k views

### How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have.
For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is $...

**17**

votes

**2**answers

953 views

### Largest graphs of girth at least 6

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6.
Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.
...

**6**

votes

**2**answers

281 views

### extremal bipartite graph

I'm facing the following question:
Given a bipartite graph $G = (L \cup R, E)$.
Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.
What is a minimal possible number ...

**2**

votes

**0**answers

196 views

### The Turán problem for graphs with given chromatic number

The ordinary Turán problem for graphs asks, "Given a graph $H$, if $G$ is an $H$-free graph on $n$ vertices, what is the largest number of edges that $G$ can have?" As is well known, if $\chi(H) = r +...

**8**

votes

**0**answers

372 views

### An extremal problem for graphs having every edge contained in a 4-clique

This is a follow-up to Graphs with many triangles but few complete graphs on 4 vertices
I'm looking for an upper bound for the difference between the number of edges and the number of 4-cliques in a ...

**0**

votes

**1**answer

102 views

### Forbidden Tripartite Graphs

I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices ...

**2**

votes

**0**answers

80 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...

**2**

votes

**0**answers

52 views

### Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...

**1**

vote

**0**answers

121 views

### What are constructions for induced $C_5$-free graphs?

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...

**7**

votes

**2**answers

442 views

### Embedding of planar graphs

I've recently come across the following lemma.
Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**4**

votes

**2**answers

214 views

### Vertex expansion of the Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is
$$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} \right\}.$$...

**0**

votes

**1**answer

237 views

### Edge-disjoint cycles in graphs

Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edge-disjoint cycles of length $k$ in $G$? If not is there a proof that this ...

**2**

votes

**2**answers

283 views

### Complete k-partite graph covers all K_k of a graph

Suppose that we have a complete graph $G$ of $n$ vertices. What is the minimum number of complete $k$-partite graph (subgraph of $G$) that covers all the complete graph of $k$ vertices of $V(G)$? Are ...

**-1**

votes

**1**answer

82 views

### Maximum degree and matching number

Let $G=(V,E)$ be a finite graph. We write $\nu(G)$ for the matching number of $G$. Is there $\varepsilon > 0$ such that we have $$\frac{\nu(G)+\Delta(G)}{V(G)} \geq \varepsilon$$ for all finite ...

**2**

votes

**1**answer

657 views

### If many triangles share edges, then some edge is shared by many triangles

Let $G=(V,E)$ be a graph.
Let $t$ denote the number of triangles in the graph, and $x$ denote the number of pairs of distinct triangles that share an edge.
(For example in $K_4$ we have $t=4$ and $x=6$...

**6**

votes

**2**answers

533 views

### Minimal graphs of prescribed girth and chromatic number

The well known result of Erdős, states that
Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$
What I am wondering is
When can we ...

**14**

votes

**1**answer

914 views

### Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality?
Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has
$$
\int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \,...

**8**

votes

**1**answer

236 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**2**

votes

**1**answer

261 views

### On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...

**9**

votes

**1**answer

456 views

### What is the correct statement of this Erdös-Gallai-Tuza problem generalizing Turan's triangle theorem?

In Zsolt Tuza's Unsolved combinatorial problems I, Problem 46 is the following conjecture:
Let $G$ be a graph on $n$ vertices. Let $\alpha_1$ be the maximum number of edges of $G$ such that every ...

**24**

votes

**3**answers

778 views

### Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...

**7**

votes

**1**answer

399 views

### Smallest Connected Graph for Given Degree Sequence

For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of non-...

**7**

votes

**0**answers

262 views

### Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...

**4**

votes

**1**answer

246 views

### Extremal graph theory for directed graphs

In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and $t(\...

**6**

votes

**1**answer

204 views

### Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.
The famous Nash-Williams conjecture claims ...

**10**

votes

**5**answers

1k views

### Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate ...

**7**

votes

**4**answers

405 views

### Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...

**6**

votes

**1**answer

150 views

### Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).
There are three main classes of criteria for Hamiltonicity that I am aware of:
Dirac-...

**5**

votes

**2**answers

275 views

### Number of trees with the same matching number

Let $\sigma(n,m)$ be the number of trees with $n$ vertices $\{ v_1, \dots, v_n \}$ such that the matching number (the size of a maximum matching) is $m$.
I have been trying to compute the value of $\...

**11**

votes

**2**answers

476 views

### Strongly connected directed graphs with large directed diameter and small undirected diameter?

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of ...

**4**

votes

**1**answer

337 views

### Extremal functions for tournaments

We are looking at directed graphs with no loops or parallel edges, but given two vertices $x$ and $y$, we allow the presence of both the edge $(x, y)$ and $(y, x)$. Thus, if $G$ is a directed graph ...

**6**

votes

**1**answer

398 views

### On Turan's theorem

Turan's theorem provides minimum number of edges of a graph on $n$ vertices to surely contain a clique of a prescribed size. This has been generalized to regular graphs.
What additional ...

**5**

votes

**1**answer

548 views

### No big clique minor but a big grid minor

I was wondering if the following result is known (or if there's a nice short proof without treewidth/brenchwidth related theorems): as the title says, suppose you have a graph without a big clique ...

**10**

votes

**0**answers

200 views

### How many n/2-cycles can a cubic graph have

Given a simple cubic graph with $n$ vertices (which implies that $n$ is even), what is a good upper bound on the number of cycles of length $n/2$ it can have?
A random cubic graph has $\Theta((4/3)^n/...

**2**

votes

**1**answer

386 views

### existence of triangle-free graphs for sparse regular graphs of degree at most n/2

It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to the half of the number of ...

**2**

votes

**0**answers

126 views

### Bipartite independence number

Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of $...

**1**

vote

**1**answer

125 views

### Distribution of Induced Subgraphs of Extremal Ramsey Graphs

Choose $k$. Let $G = (V,E)$ be a graph on $n = R(k,k)-1$ vertices (that is, $G$ is an extremal example for $R(k,k)$, and $g : E \to \{r, b\}$ be an edge 2-coloring such that there is no monochromatic $...