Re: vertices in graph vertex covers

From: Russell Easterly (logiclab_at_comcast.net)
Date: 03/24/05 

Date: Thu, 24 Mar 2005 03:00:13 +0000 (UTC)

"Jean Cardinal" <jcardin@ulb.ac.be> wrote in message
news:d1c8lu$dn$1@dizzy.math.ohio-state.edu...
>
> I am looking for references on the following idea.
>
> We consider a simple undirected graph (V,E), and its set of minimum
> vertex covers, i.e. the set of all minimum-size subsets S of V such
> that every edge in E has at least one endpoint in S.
>
> We classify the vertices in three categories:
> A : vertices that are not contained in any minimum vertex cover,
> B : vertices that are contained in some minimum vertex covers, but not
> all,
> C : vertices that are contained in all minimum vertex covers.
>
> It is easy to see that edges can only have pairs of endpoints of the
> form AC, BB, BC or CC. If an edge would be of type AB, for instance,
> then it would mean that it is not covered in some minimum vertex
> covers, a contradiction. This observation implies in particular that
> the set of A-vertices is an independent set.
>
> What else can be said?

I can say a lot of things you
have probably already thought of.

Vertex v must be in the cover or
the neighbor set of v, NS(v), must
be in the cover. If v is in set A
then NS(v) must be in C.
(Converse, if NS(v) is in set C
then v must be in A.)

It is easy to come up with graphs
where every vertex is in set B.
A graph where every vertex is of degree 2
is an example.

I think the following is true.
For bipartite graphs, all vertices are
in set B or no vertices are in set B.

A bipartite graph can be broken into two
partitions such that no vertex in
a partition shares an edge with another
vertex in that partition.

Each partition is a vertex cover and at
least one of them is a minimal vertex cover.
If the two partitions are the same size
then all vertices are in your set B.
Otherwise, the smaller partition is in set C
and the larger partition is in set A.

To complete the proof I would have to
show there is only one way to partition
a bipartite graph.

Your method is similar to somthing I have
been studying.

We start with a Boolean Satisfaction instance, F(),
derived from a set of variables, V().
Consider the set of satisfying assignments for F(),

We classify the variables in V() into three categories:

Fixed: Variables that have the same assignment
in every satisfying assignment.

Dependent: A variable where the assignment depends on
the assignment of another variable (The other variable
can't be a fixed variable)

Independent: For every satisfying assignment where v
is True, there is an identical satisfying assignment
except v is False.

Fixed variables are similar to your set C.
Since every variable has an assignment there is
no classification corresponding to your set A.

Independent variables are a subset of dependent
variables. Think of an indepedent variable as
a dependent variable that depends on the empty set.
If a SAT problem were reduced to the minimum
number of variables all of the indepedent
vriables would be removed.

SAT instances can be converted to minimal vertex
cover problems. So, both our methods could be used to
describe graphs representing SAT problems.

Russell
- 2 many 2 count

Relevant Pages

  • Constructing Quotient Graphs
    ... If we partition N into k parts. ... We define the "Quotient graph" with respect to the above partition as: ... running time O+size). ...
    (comp.programming)
  • Graph Partitioning Problem
    ... I have an application where I want to find a minimum weight partition ... of an undirected graph into k connected components such that each ... All the graph partitioning algorithms and programs I've seen ... Does anybody know of any algorithms, ...
    (comp.theory)
  • Graph Theory: Cuts, Minimal Cuts and Bonds
    ... These definitions are from Reinhard Diestel's "Graph Theory, ... minimal or maximal sets of vertices or edges, ... We denote the set of this edges in E (edge set of ... partition is called a cut. ...
    (sci.math)
  • Re: combinatorics/graph theory problem for set partitions
    ... >Suppose I construct a random graph by choosing k edges in such a way ... >that each edge is chosen independently with probability p, ... >Then I consider the set partition defined by this graph such that two ...
    (sci.stat.math)
  • Re: combinatorics/graph theory problem for set partitions
    ... >Suppose I construct a random graph by choosing k edges in such a way ... >that each edge is chosen independently with probability p, ... >Then I consider the set partition defined by this graph such that two ...
    (sci.math)