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
add comment

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.