Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Price of Connectivity for Vertex Cover   The vertex cover number of a graph is the minimum number of vertices that are
needed to cover all edges. When those vertices are further required to induce a
connected subgraph, the corresponding number is called the connected vertex
cover number, and is always greater or equal to the vertex cover number.
  Connected vertex covers are found in many applications, and the relationship
between those two graph invariants is therefore a natural question to
investigate. For that purpose, we introduce the {\em Price of Connectivity},
defined as the ratio between the two vertex cover numbers. We prove that the
price of connectivity is at most 2 for arbitrary graphs. We further consider
graph classes in which the price of connectivity of every induced subgraph is
bounded by some real number $t$. We obtain forbidden induced subgraph
characterizations for every real value $t \leq 3/2$.
  We also investigate critical graphs for this property, namely, graphs whose
price of connectivity is strictly greater than that of any proper induced
subgraph. Those are the only graphs that can appear in a forbidden subgraph
characterization for the hereditary property of having a price of connectivity
at most $t$. In particular, we completely characterize the critical graphs that
are also chordal.
  Finally, we also consider the question of computing the price of connectivity
of a given graph. Unsurprisingly, the decision version of this question is
NP-hard. In fact, we show that it is even complete for the class $\Theta_2^P =
P^{NP[\log]}$, the class of decision problems that can be solved in polynomial
time, provided we can make $O(\log n)$ queries to an NP-oracle. This paves the
way for a thorough investigation of the complexity of problems involving ratios
of graph invariants.

34
The categories of this paper are: chem-ph
35
The categories of this paper are: mtrl-th
8
The categories of this paper are: hep-ex
20
The categories of this paper are: acc-phys
28
The categories of this paper are: alg-geom
26
The categories of this paper are: bayes-an
32
The categories of this paper are: atom-ph
19
The categories of this paper are: eess
30
The categories of this paper are: q-alg
22
The categories of this paper are: chao-dyn
27
The categories of this paper are: comp-gas
33
The categories of this paper are: plasm-ph
10
The categories of this paper are: q-bio
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
25
The categories of this paper are: patt-sol