Study of graphs satisfying a property that are maximal or minimal with respect to some parameter. A classic example is Turán's Theorem, which exactly characterizes the densest graphs on $n$ vertices without a $K_t$ subgraph.

learn more… | top users | synonyms

6
votes
1answer
434 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 ≥ ...
0
votes
1answer
254 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 ...
9
votes
0answers
195 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 ...
8
votes
0answers
368 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 ...
7
votes
0answers
260 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 ...
6
votes
0answers
370 views

Cliques of hyperedges

Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two ...
4
votes
0answers
428 views

Smallest matrix covered by many random n by n matrices

We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...
2
votes
0answers
77 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
0answers
51 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, ...
2
votes
0answers
193 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 ...
2
votes
0answers
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 ...
2
votes
0answers
127 views

Smallest size for an incomplete tournament with property $S_k$

By a well-known probabilistic argument due to Erdos, if $k>1$ is an integer then for all large enough $n$, there an asymmetric relation $R$ on $X=\lbrace 1,2, \ldots ,n \rbrace$ (i.e. $R \subseteq ...
1
vote
0answers
75 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 ...
1
vote
0answers
118 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, ...
1
vote
0answers
270 views

graphs with maximal number of paths of given length

Hi, For a given number of edges, the non directed graph which maximises the number of paths of length 2 is the quasi-star or the quasi-complete graph. Does anyone know : 1- what is the non directed ...
0
votes
0answers
57 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 ...