Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $C$ be the class of graphs of girth $g$ or more. $C$ can alternatively be characterized as: $G \in C$ iff each of $G$'s vertex induced subgraphs on less than $g$ nodes is a forest.

We can generalize this as follows. Let $A$ be a class of graphs. Define $C_A$ as: $G \in C_A(k)$ iff all of $G$'s vertex induced subgraphs on less than $k$ nodes are members of $A$.

A natural question is then:

Given a class of graphs $A$ and integer $k$ how many graphs on $n$ vertices are in $C_A(k)$? Or more generally, can one bound the number of graphs on $n$ vertices in $C_A(k)$ given $k$ and $A$?

The particular situation I am interested in is where we allow $k$ to be a function of the number of vertices in the graph. That is let $C_A(f(n))$ (where $f(n) < n$) be defined as: $G \in C_A(f(n))$ iff all of $G$'s vertex induced subgraphs on less than $f(n)$ vertices are members of $A$ (where $n$ is the number of vertices in $G$).

My actual question is: Is there a class of graphs $A$ such that the number of graphs in $A$ on $n$ vertices is $2^{O(g(n))}$ but the number of graphs on $n$ vertices in $C_A(c \cdot g^{-1}(n))$ is $2^{\omega(g(n))}$, for some constant $c$? Stated another way: all vertex induced subgraphs on $n$ vertices of a graph on $g(n)$ vertices in $C_A(c \cdot g^{-1}(n))$ are in $A$.

In particular I am interested in the situation where $g(n) = n\log{n}$ and $A$ is hereditary (every vertex induced subgraph of a graph in $A$ is also in $A$). This implies that all vertex induced subgraphs of size $n$ or less of a graph on $n\log{n}$ vertices in $C_A(g^{-1}(n))$ are in $A$.

EDIT: My motivation for this question is that it is related to an open problem on implicit graph representation in: S. Kannan, M. Naor, S. Rudich, Implicit Representation of Graphs, SIAM Journal on Discrete Mathematics 5, 596-603, 1992

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.