The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
591 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 ...
9
votes
2answers
695 views

Number of Geodesic Paths Passing Through a Vertex in an Expander Graph

Let $\{G_{n}\}$ be a sequence of $k$-regular expander graphs. For each $n$ assume that each pair of nodes in the graph is transmitting a unit load of traffic and the traffic goes through the minimum ...
8
votes
1answer
390 views

What is the state of the art for the Turán number of $K_{4,4}$?

In Chung and Graham's "Erdős on Graphs: His legacy of unsolved problems," they discuss several open problems concerning Turán numbers for bipartite graphs. There is a construction which gives graphs ...
2
votes
0answers
117 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 ...
5
votes
1answer
607 views

Connected components of large induced subgraphs of hypercubes

Let $H$ be the $n$-dimensional hypercube, i.e. $\{0,1\}^n$ with edges between two vertices if and only if they differ in exactly one co-ordinate. We say that an edge is in direction $i$ if its ...
5
votes
1answer
545 views

Characterization of infinite paths in graphs

First an introduction. A directed graph we all know what is, and a graph is serial whenever every vertex has a successor. I do not consider the empty graph. A pair $(\mathcal{G},s)$ is called a ...
4
votes
0answers
320 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
1answer
415 views

Graphs with many triangles but few complete graphs on 4 vertices

Let $G$ be a graph on $n$ vertices with $an^2$ edges containing at most $an^2/2$ copies of $K_4$. If there are cubically many triangles, say $cn^3$, then there is at least one edge that is not ...
21
votes
4answers
934 views

A graph with few edges everywhere

Given a graph $G(V,E)$ whose edges are colored in two colors: red and blue. Suppose the following two conditions hold: for any $S\subseteq V$, there are at most $O(|S|)$ red edges in $G[S]$ for any ...
2
votes
1answer
382 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 ...
1
vote
1answer
278 views

Graphs far from being a collection of bicliques

A biclique is a complete bipartite graph. A graph is a "biclique collection" if it can be decomposed into the disjoint union of bicliques. Denote the set of such graphs by $\mathcal{BCC}$. Given a ...
5
votes
3answers
869 views

Online Library of Unlabeled Connected Graphs on n Vertices

Does anyone know of the link to an online library of of unlabeled, connected graphs on n vertices? I remember looking at such an archive a few years ago while at a Macaulay 2 workshop, but I've been ...
6
votes
0answers
357 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 ...
1
vote
2answers
469 views

Bounds on the independence number of a graph

If $G$ is a graph with $n$ vertices and $\frac{nk}{2}$ edges, $k\ge -1,$ then $a(G)\ge \frac{n}{k+1}$. Why? (Here $a(G)$ is the independence number).
6
votes
2answers
483 views

Is the feedback vertex number bounded by the maximum number of leaves in a spanning tree?

I have a graph-theoretical conjecture which I think would have been studied before, but for which I cannot find anything in the literature. Let G be a finite, simple, connected graph. Let the ...
2
votes
1answer
379 views

Suppose the independent number of a graph is bounded. How small the clique number can be?

Suppose the independent number of a graph is bounded. How small the clique number can be? linear? It seems to be a natural problem to ask. but I could not find any reference. Thanks.
1
vote
2answers
453 views

Minimal Non-planar Extensions of a Graph

Given a planar graph $G=(V,E)$ with vertices $V$ and edges $E$, call $\bar G = (V,\bar E)$ a non-planar extension of $G$ if $\bar G$ is non-planar and $E \subset \bar E$. I'm interested in minimal ...
4
votes
3answers
837 views

Erdős–Stone theorem type edge density estimates for bipartite graphs?

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically. However, ...