Source author record

Dalu Jacob

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

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

New bounds on the anti-Ramsey numbers of star graphs

The anti-Ramsey number $ar(G,H)$ with input graph $G$ and pattern graph $H$ , is the maximum positive integer $k$ such that there exists an edge coloring of $G$ using $k$ colors, in which there are no rainbow subgraphs isomorphic to $H$ in $G$ . ( $H$ is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdös, Simanovitz, and Sós in 1973. Thereafter several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph $K_{1,t}$ (for $t \geq 3$ ) purely from an algorithmic point of view due to its applications in interference modeling of wireless networks. They posed it as an optimization problem, the maximum edge $q$ -coloring problem. For a graph $G$ and an integer $q\geq 2$ , an edge $q$ -coloring of $G$ is an assignment of colors to edges of $G$ , such that edges incident on a vertex span at most $q$ distinct colors. The maximum edge $q$ -coloring problem seeks to maximize the number of colors in an edge $q$ -coloring of the graph $G$ . Note that the optimum value of the edge $q$ -coloring problem of $G$ equals $ar(G,K_{1,q+1})$ . In this paper, we study $ar(G,K_{1,t})$ , the anti-Ramsey number of stars, for each fixed integer $t\geq 3$ , both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for $ar(G,K_{1,q+1})$ , in terms of number of vertices and the minimum degree of $G$ . The second one improves this result for the case of triangle-free input graphs. For a positive integer $t$ , let $H_t$ denote a subgraph of $G$ with maximum number of possible edges and maximum degree $t$ . Our third main result presents an upper bound for $ar(G,K_{1,q+1})$ in terms of $|E(H_{q-1})|$ . All our results have algorithmic consequences.

preprint2016arXiv

Uniquely Restricted Matchings in Interval Graphs

A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$ . We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. ("Uniquely restricted matchings", M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality "strong independent set" in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.

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.