Information Technology Reference
In-Depth Information
depending on the total number of edges rather than the maximum degree, our
algorithms are sensitive to graphs with heterogeneous vertex degrees, and can
construct larger induced subgraphs when the number of high-degree vertices is
relatively small. Additionally, the algorithm given by Edwards and Farr is slower
than ours, taking
O
(
mn
) time. In a follow-up paper, Morgan and Farr [16] gave
additional bounds on induced outerplanar subgraphs, and provided experimental
results on the performance of their algorithms. A second paper by Edwards and
Farr [8], like our Theorem 2, gives bounds on the size of the largest induced
partial 2-tree in terms of
n
and
m
,whichis
3
n
2
m/n
+1
2
n
. However,
their bounds are asymptotically worse than Theorem 2 when 2
n<m<
2
.
5
n
and require an additional assumption of connectivity for smaller values of
m
.
A third paper by the same authors [9] gives improved bounds that are more
dicult to state as a formula.
For some other graph classes than the ones we study, it is possible to prove
trivial bounds on the size of the largest induced subgraph in the class, of a
similar form to the bounds of Alon et al. and of our theorems. By repeatedly
finding and removing a vertex of degree
for
m
≥
≥
1, one can obtain an independent set
of at least
n
m
vertices, and the example of a perfect matching shows this to
be tight. By repeatedly finding and removing a vertex of degree
−
≥
2, one can
obtain a matching of at least
n
m/
2 vertices, and the example of the disjoint
union of
n/
3 two-edge paths shows this to be tight. And by repeatedly finding
and removing either a vertex of degree
−
3 or a vertex that is part of a 2-regular
cycle, one can obtain a linear forest (forest with maximum degree 2) of
n
≥
m/
3
vertices; the example of the disjoint union of
n/
3 triangles shows this to be tight
even for more general forests.
Table 1 provides a comparison of these new results with previous known results
on induced planar subgraphs of various types and with the trivial bounds for
independent sets, matchings, and linear forests.
−
2 Preliminaries
For a graph
G
, we define
n
(
G
) to be the number of vertices and
m
(
G
)tobe
the number of edges in
G
. We drop the argument and write
n
and
m
when the
choice of
G
is clear from context.
A subset
S
of the vertices of
G
corresponds to an
induced subgraph G
[
S
], a
graph having
S
as its vertices and having as edges every edge in
G
that has both
endpoints in
S
.Equivalently,
G
[
S
] may be constructed from
G
by deleting every
vertex that is not in
S
and every edge that has at least one endpoint outside
S
.
A
pseudoforest
is an undirected graph in which every connected component
has at most one cycle. Equivalently, the pseudoforests can be formed from forests
(acyclic undirected graphs) by adding at most one edge per connected compo-
nent. A
k-tree
is an undirected graph that can be constructed from a
K
k
graph
by repeatedly picking a
K
k
subgraph and attaching its
k
vertices to a new vertex.
A
partial k-tree
is a subgraph of a
k
-tree and is said to have
treewidth
at most
k
; the treewidth of a graph
G
is denoted tw(
G
). Every pseudoforest is a partial
