5
$\begingroup$

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

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.