All Questions
9 questions
3
votes
1
answer
158
views
Sharp upper bound of the number of edges for graphs of thickness two
A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
- 1,075
0
votes
0
answers
55
views
Comparing spectral radius of two graphs using the entry of Perron vector
Suppose we have a graph $G$.
Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector.
Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$.
We ...
- 199
1
vote
0
answers
79
views
Partitioning of a set family that avoids small intersections
Let $\mathcal{F}$ be the family of all $k$-element subsets of $[n]$. What is the smallest $\ell$ such that we can partition $\mathcal{F}$ into $\ell$ families $F_1,\dots,F_\ell$ with the property that ...
- 135
10
votes
1
answer
526
views
Maximum number of triangles no two of which have a common edge
For $n\in N_+$, define $f(n)$ to be the maximum number of triangles in a graph $G$ with $n$ vertices, taken over all $n$-vertex graphs having the property where no two triangles have a common edge.
Do ...
- 475
1
vote
0
answers
54
views
Constructing graphs from subsets of a minimal alphabet
From an alphabet of $N$ letters, choose $n$ pairwise distinct subsets $ v_1,\dots,v_n$ of a fixed size $k$ and define a graph on $V=\{v_1,\dots,v_n\}$, which has an edge for each pair of vertices that ...
- 13.4k
1
vote
1
answer
299
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 ...
- 11
0
votes
1
answer
398
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 ...
- 1,129
2
votes
0
answers
78
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, ...
5
votes
2
answers
383
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(\...
- 131