Please click here to download the publication list in pdf file.

Sort by year:

Submitted Paper Submitted for possible journal publication

Journal Paper Journal of Graph Theory 83(3) (2016), 231-250

An induced matching in a graph is a set of edges whose
endpoints induce a 1-regular subgraph. It is known that every n-vertex graph has at most 10^{n/5} ≈ 1.5849^{n} maximal induced matchings, and this bound is the best possible. We prove that every n-vertex triangle-free graph has at most 3^{n/3} ≈ 1.4423^{n} maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K_{3,3}. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time O(1.4423^{n}), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

Journal Paper Information Processing Letters 115(9) (2015), 671 - 676

The metric dimension of a graph G is the smallest size of a set R of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in R. Computing the metric dimension is NP-hard, even when restricting inputs to bipartite graphs. We present a linear-time algorithm for computing the metric dimension for chain graphs, which are bipartite graphs whose vertices can be ordered by neighborhood inclusion.

Journal Paper Theory of Computing Systems 57(1) (2015), 140 - 159

The well-known DISJOINT PATHS problem takes as input a graph G and
a set of k pairs of terminals in G, and the task is to decide whether there exists a
collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. This problem is known
to be NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k
due to a celebrated result by Robertson and Seymour, it is known not to admit a
polynomial kernel unless NP ⊆ coNP/poly. We prove that DISJOINT PATHS remains
NP-complete on split graphs, and show that the problem admits a kernel with O(k^{2})
vertices when restricted to this graph class. We furthermore prove that, on split
graphs, the edge-disjoint variant of the problem is also NP-complete and admits a
kernel with O(k^{3}) vertices. To the best of our knowledge, our kernelization results
are the first non-trivial kernelization results for these problems on graph classes.

For a graph class G and any two positive integers i and j, the Ramsey number RG(i, j) is the
smallest positive integer such that every graph in G on at least R_{G}(i, j) vertices has a clique
of size i or an independent set of size j. For the class of all graphs, Ramsey numbers are
notoriously hard to determine, and they are known only for very small values of i and j.
Even if we restrict G to be the class of claw-free graphs, it is highly unlikely that a formula
for determining R_{G}(i, j) for all values of i and j will ever be found, as there are infinitely
many nontrivial Ramsey numbers for claw-free graphs that are as difficult to determine
as for arbitrary graphs. Motivated by this difficulty, we establish here exact formulas for
all Ramsey numbers for three important subclasses of claw-free graphs: line graphs, long
circular interval graphs, and fuzzy circular interval graphs. On the way to obtaining these
results, we also establish all Ramsey numbers for the class of perfect graphs. Such positive
results for graph classes are rare: a formula for determining R_{G}(i, j) for all values of i
and j, when G is the class of planar graphs, was obtained by Steinberg and Tovey (1993),
and this seems to be the only previously known result of this kind. We complement our
aforementioned results by giving exact formulas for determining all Ramsey numbers for
several graph classes related to perfect graphs.

Journal PaperJournal of Discrete Algorithms 26 (2014), 7 - 15

Given a graph G = (V , E) and a set S ⊆ V , a set U ⊆ V is a subset feedback vertex set
of (G, S) if no cycle in G[V \ U] contains a vertex of S. The Subset Feedback Vertex Set
problem takes as input G, S, and an integer k, and the question is whether (G, S) has
a subset feedback vertex set of cardinality or weight at most k. Both the weighted and
the unweighted versions of this problem are NP-complete on chordal graphs, even on their
subclass split graphs. We give an algorithm with running time O(1.6708^{n}) that enumerates
all minimal subset feedback vertex sets on chordal graphs on n vertices. As a consequence,
Subset Feedback Vertex Set can be solved in time O(1.6708^{n}) on chordal graphs, both in
the weighted and in the unweighted case. As a comparison, on arbitrary graphs the fastest
known algorithm for these problems has O(1.8638^{n}) running time. We also obtain that
a chordal graph G has at most 1.6708^{n} minimal subset feedback vertex sets, regardless
of S. This narrows the gap with respect to the best known lower bound of 1.5848n on this
graph class. For arbitrary graphs, the gap is substantially wider, as the best known upper
and lower bounds are 1.8638^{n} and 1.5927^{n}, respectively.

Conference PaperWG 2014, LNCS 8747: 93-104, Springer

An induced matching in a graph is a set of edges whose
endpoints induce a 1-regular subgraph. It is known that every n-vertex
graph has at most 10^{n/5} ≈ 1.5849^{n} maximal induced matchings, and this
bound is best possible. We prove that every n-vertex triangle-free graph
has at most 3^{n/3} ≈ 1.4423^{n} maximal induced matchings, and this bound
is attained by every disjoint union of copies of the complete bipartite
graph K_{3,3}. Our result implies that all maximal induced matchings in an
n-vertex triangle-free graph can be listed in time O(1.4423^{n}), yielding
the fastest known algorithm for finding a maximum induced matching in
a triangle-free graph.

The well-known Disjoint Paths problem takes as input a
graph G and a set of k pairs of terminals in G, and the task is to decide
whether there exists a collection of k pairwise vertex-disjoint paths in G
such that the vertices in each terminal pair are connected to each other
by one of the paths. This problem is known to NP-complete, even when
restricted to planar graphs or interval graphs. Moreover, although the
problem is fixed-parameter tractable when parameterized by k due to a
celebrated result by Robertson and Seymour, it is known not to admit
a polynomial kernel unless NP ⊆ coNP/poly. We prove that Disjoint
Paths remains NP-complete on split graphs, and show that the problem
admits a kernel with O(k^{2}) vertices when restricted to this graph class.
We furthermore prove that, on split graphs, the edge-disjoint variant of
the problem is also NP-complete and admits a kernel with O(k^{3}) vertices.
To the best of our knowledge, our kernelization results are the first nontrivial kernelization results for these problems on graph classes.

The closed neighborhood N_{G}[e] of an edge e in a graph G is the set consisting of e
and of all edges having a common end-vertex with e. Let f be a function on E(G), the
edge set of G, into the set {-1, 1}. If ∑_{x∈ N[e]} f(x) ≥ 1 for at least k edges e of G, then
f is called a signed edge k-subdominating function of G. The minimum of the values
∑_{e∈ E(G)} f(e), taken over all signed edge k-subdominating function f of G, is called
the signed edge k-subdomination number of G and is denoted by γ'_{ks} (G). In this note
we initiate the study of the signed edge k-subdomination in graphs and present some
(sharp) bounds for this parameter.

Conference PaperIPEC 2012, LNCS 7535: 85 - 96, Springer

Given a graph G = (V, E) and a set S ⊆ V , a set U ⊆ V is a
subset feedback vertex set of (G, S) if no cycle in G[V \U] contains a vertex
of S. The Subset Feedback Vertex Set problem takes as input G, S,
and an integer k, and the question is whether (G, S) has a subset feedback
vertex set of cardinality or weight at most k. Both the weighted and the
unweighted versions of this problem are NP-complete on chordal graphs,
even on their subclass split graphs. We give an algorithm with running
time O(1.6708^{n}) that enumerates all minimal subset feedback vertex sets
on chordal graphs with n vertices. As a consequence, Subset Feedback
Vertex Set can be solved in time O(1.6708^{n}) on chordal graphs, both in
the weighted and in the unweighted case. On arbitrary graphs, the fastest
known algorithm for the problems has O(1.8638^{n}) running time.

Conference PaperCOCOON 2012, (**Best Paper Award**), LNCS 7434: 204 - 215, Springer

For any graph class G and any two positive integers i and j,
the Ramsey number R_{G}(i,j) is the smallest integer such that every graph
in G on at least R_{G}(i,j) vertices has a clique of size i or an independent set
of size j. For the class of all graphs Ramsey numbers are notoriously hard
to determine, and the exact values are known only for very small integers
i and j. For planar graphs all Ramsey numbers can be determined by an
exact formula, whereas for claw-free graphs there exist Ramsey numbers
that are as difficult to determine as for arbitrary graphs. No further
graph classes seem to have been studied for this purpose. Here, we give
exact formulas for determining all Ramsey numbers for various classes
of graphs. Our main result is an exact formula for all Ramsey numbers
for line graphs, which form a large subclass of claw-free graphs and are
not perfect. We obtain this by proving a general result of independent
interest: an upper bound on the number of edges any graph can have if
it has bounded degree and bounded matching size. As complementary
results, we determine all Ramsey numbers for perfect graphs and for
several subclasses of perfect graphs.

An induced matching in a graph is a set of edges whose endpoints
induce a 1-regular subgraph. It is known that any n-vertex graph has at most
10^{n/5} ≈ 1.5849^{n} maximal induced matchings, and this bound is best possible.
We prove that any n-vertex triangle-free graph has at most 3^{n/3} ≈ 1.4423^{n}
maximal induced matchings, and this bound is attained by any disjoint union
of copies of the complete bipartite graph K_{3,3}. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time
O(1.4423^{n}), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

Journal PaperAKCE International Journal of Graphs and Combinatorics 8 (2011), 1 - 11

The closed neighborhood N_{G}[e] of an edge e in a graph G is the set consisting of
e and of all edges having a common end-vertex with e. Let f be a function on E(G),
the edge set of G, into the set {-1, 0, 1}. If ∑_{x∈ N[e]} f(x) ≥ 1 for at least k edges e
of G, then f is called a minus edge k-subdominating function of G. The minimum of
the values ∑_{e∈ E(G)} f(e), taken over all minus edge k-subdominating functions f of G,
is called the minus edge k-subdomination number of G and is denoted by γ'_{km}(G). In
this note we initiate the study of minus edge k-subdomination numbers in graphs and
present some (sharp) bounds for this parameter.

Let G be a simple graph without isolated vertices with vertex set
V (G) and edge set E(G), b be a positive integer and k an integer with
1 ≤ k ≤ |V (G)|. A function f : E(G) → {-1, 1} is said to be a signed
(b, k)-matching of G if ∑_{e∈ E(v)} f(e) ≤ b for at least k vertices v of G,
where E(v) is the set of all edges at v. The value max ∑_{e∈ E(G)} f(e),
taking over all signed (b,k)-matching f of G, is called the signed (b, k)-
matching number of G and is denoted by β'_{(b,k)}(G). In this paper we
initiate the study of the signed (b,k)-matching number in graphs and
present some bounds for this parameter.

Journal PaperIntelligent Information Management 2 (2010), 143 - 148

Let G be a simple graph with vertex set V(G) and edge set E(G). Let G have at least k vertices of
degree at least b, where k and b are positive integers. A function f : E(G) → {-1,1} is said to be a
signed (b,k)-edge cover of G if ∑_{e∈E(v)} f(e) ≥ b for at least k vertices of G, where E(v)={uv ∈ E(G) | u ∈ N(v)}. The value min∑_{e∈E(G)} f(e), taking over all signed (b,k)-edge covers f of G
is called the signed (b,k)-edge cover number of G and denoted by ρ'_{b,k}(G).
In this paper we give some bounds on the signed (b,k)-edge cover number of graphs.

Journal PaperAKCE International Journal of Graphs and Combinatorics 6 (2009), 361 - 371

Let G be a simple connected graph without isolated vertex with vertex set V(G) and edge
set E(G). A function f : V (G) → {-1, 1} is said to be a negative k-subdecision function of G
if ∑_{x∈NG(v)} f(x) ≤ 1 for at least k vertices v of G. The value max∑_{x∈V(G)} f(x), taking over all negative k-subdecision functions f of G, is called the negative k-subdecision number of G
and is denoted by β_{kD}(G). In this paper we initiate the study of the negative k-subdecision
numbers in graphs and present some bounds for this parameter.

Journal PaperDiscrete Applied Mathematics 156 (2008), 3066 - 3070

Let G be a simple graph without isolated vertex with vertex set V(G) and edge set E(G). A function f : E(G) → {-1, 1}
is said to be a signed star k-subdominating function of G if ∑_{e∈E(v)} f(e) ≥ 1 for at least k vertices v of G, where
E(v) = {uv ∈ E(G) | u ∈ N(v)}. The value min∑_{e∈E(G)} f(e), taking over all signed star k-subdominating function f of G is called the signed star k-subdomination number of G and denoted by γ^{k}_{SS}(G). In this paper we give some bounds on the signed star k-subdomination number of graphs.