Source author record

Eglantine Camby

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

3works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

A new characterization of $P_k$ -free graphs

The class of graphs that do not contain an induced path on $k$ vertices, $P_k$ -free graphs, plays a prominent role in algorithmic graph theory. This motivates the search for special structural properties of $P_k$ -free graphs, including alternative characterizations. Let $G$ be a connected $P_k$ -free graph, $k \ge 4$ . We show that $G$ admits a connected dominating set whose induced subgraph is either $P_{k-2}$ -free, or isomorphic to $P_{k-2}$ . Surprisingly, it turns out that every minimum connected dominating set of $G$ has this property. This yields a new characterization for $P_k$ -free graphs: a graph $G$ is $P_k$ -free if and only if each connected induced subgraph of $G$ has a connected dominating set whose induced subgraph is either $P_{k-2}$ -free, or isomorphic to $C_k$ . This improves and generalizes several previous results; the particular case of $k=7$ solves a problem posed by van 't Hof and Paulusma [A new characterization of $P_6$ -free graphs, COCOON 2008]. In the second part of the paper, we present an efficient algorithm that, given a connected graph $G$ on $n$ vertices and $m$ edges, computes a connected dominating set $X$ of $G$ with the following property: for the minimum $k$ such that $G$ is $P_k$ -free, the subgraph induced by $X$ is $P_{k-2}$ -free or isomorphic to $P_{k-2}$ . As an application our results, we prove that Hypergraph 2-Colorability, an NP-complete problem in general, can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graph is $P_7$ -free.

preprint2013arXiv

A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles

The ratio of the connected domination number, $γ_c$ , and the domination number, $γ$ , is strictly bounded from above by 3. It was shown by Zverovich that for every connected $(P_5,C_5)$ -free graph, $γ_c = γ$ . In this paper, we investigate the interdependence of $γ$ and $γ_c$ in the class of $(P_k,C_k)$ -free graphs, for $k \ge 6$ . We prove that for every connected $(P_6,C_6)$ -free graph, $γ_c \le γ+ 1$ holds, and there is a family of $(P_6,C_6)$ -free graphs with arbitrarily large values of $γ$ attaining this bound. Moreover, for every connected $(P_8,C_8)$ -free graph, $γ_c / γ\le 2$ , and there is a family of $(P_7,C_7)$ -free graphs with arbitrarily large values of $γ$ attaining this bound. In the class of $(P_9,C_9)$ -free graphs, the general bound $γ_c / γ\le 3$ is asymptotically sharp.

preprint2013arXiv

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 $Θ_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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Eglantine Camby

Research overview

Is this your work?

3 publications

A new characterization of $P_k$ -free graphs

A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles

The Price of Connectivity for Vertex Cover

See the researcher in context

Building this map preview

Eglantine Camby

Research overview

Is this your work?

3 publications

A new characterization of PkP_kPk​-free graphs

A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles

The Price of Connectivity for Vertex Cover

See the researcher in context

Building this map preview

A new characterization of $P_k$ -free graphs