Source author record

Deepak Rajendraprasad

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms Computational Complexity math.AT

Catalog footprint

Research overview

27works

5topics

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.

preprint2022arXiv

Disjoint Total Dominating Sets in Near-Triangulations

We show that every simple planar near-triangulation with minimum degree at least three contains two disjoint total dominating sets. The class includes all simple planar triangulations other than the triangle. This affirms a conjecture of Goddard and Henning [Thoroughly dispersed colorings, J. Graph Theory, 88 (2018) 174-191].

preprint2020arXiv

A Note on Arc-Disjoint Cycles in Bipartite Tournaments

We show that for each non-negative integer k, every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7(k - 1).

preprint2020arXiv

An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter

An orientation of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$ . The oriented diameter of a graph $G$ is the smallest diameter among all the orientations of $G$ . The maximum oriented diameter of a family of graphs $\mathscr{F}$ is the maximum oriented diameter among all the graphs in $\mathscr{F}$ . Chvátal and Thomassen [JCTB, 1978] gave a lower bound of $\frac{1}{2}d^2+d$ and an upper bound of $2d^2+2d$ for the maximum oriented diameter of the family of $2$ -edge connected graphs of diameter $d$ . We improve this upper bound to $1.373 d^2 + 6.971d-1$ , which outperforms the former upper bound for all values of $d$ greater than or equal to $8$ . For the family of $2$ -edge connected graphs of diameter $3$ , Kwok, Liu and West [JCTB, 2010] obtained improved lower and upper bounds of $9$ and $11$ respectively. For the family of $2$ -edge connected graphs of diameter $4$ , the bounds provided by Chvátal and Thomassen are $12$ and $40$ and no better bounds were known. By extending the method we used for diameter $d$ graphs, along with an asymmetric extension of a technique used by Chvátal and Thomassen, we have improved this upper bound to $21$ .

preprint2020arXiv

Characterization and a 2D Visualization of B $_0$ -VPG Cocomparability Graphs

B $_0$ -VPG graphs are intersection graphs of vertical and horizontal line segments on a plane. Cohen, Golumbic, Trotter, and Wang [Order, 2016] pose the question of characterizing B $_0$ -VPG permutation graphs. We respond here by characterizing B $_0$ -VPG cocomparability graphs. This characterization also leads to a polynomial time recognition and B $_0$ -VPG drawing algorithm for the class. Our B $_0$ -VPG drawing algorithm starts by fixing any one of the many posets $P$ whose cocomparability graph is the input graph $G$ . The drawing we obtain not only visualizes $G$ in that one can distinguish comparable pairs from incomparable ones, but one can also identify which among a comparable pair is larger in $P$ from this visualization.

preprint2020arXiv

Dimension of CPT posets

A collection of linear orders on $X$ , say $\mathcal{L}$ , is said to \emph{realize} a partially ordered set (or poset) $\mathcal{P} = (X, \preceq)$ if, for any two distinct $x,y \in X$ , $x \preceq y$ if and only if $x \prec_L y$ , $\forall L \in \mathcal{L}$ . We call $\mathcal{L}$ a \emph{realizer} of $\mathcal{P}$ . The \emph{dimension} of $\mathcal{P}$ , denoted by $dim(\mathcal{P})$ , is the minimum cardinality of a realizer of $\mathcal{P}$ . A \emph{containment model} $M_{\mathcal{P}}$ of a poset $\mathcal{P}=(X,\preceq)$ maps every $x \in X$ to a set $M_x$ such that, for every distinct $x,y \in X,\ x \preceq y$ if and only if $M_x \varsubsetneq M_y$ . We shall be using the collection $(M_x)_{x \in X}$ to identify the containment model $M_{\mathcal{P}}$ . A poset $\mathcal{P}=(X,\preceq)$ is a Containment order of Paths in a Tree (CPT poset), if it admits a containment model $M_{\mathcal{P}}=(P_x)_{x \in X}$ where every $P_x$ is a path of a tree $T$ , which is called the host tree of the model. We show that if a poset $\mathcal{P}$ admits a CPT model in a host tree $T$ of maximum degree $Δ$ and radius $r$ , then \rogers{ $dim(\mathcal{P}) \leq \lg\lg Δ+ (\frac{1}{2} + o(1))\lg\lg\lg Δ+ \lg r + \frac{1}{2} \lg\lg r + \frac{1}{2}\lg π+ 3$ . This bound is asymptotically tight up to an additive factor of $\min(\frac{1}{2}\lg\lg\lg Δ, \frac{1}{2}\lg\lg r)$ . Further, let $\mathcal{P}(1,2;n)$ be the poset consisting of all the $1$ -element and $2$ -element subsets of $[n]$ under `containment' relation and let $dim(1,2;n)$ denote its dimension. The proof of our main theorem gives a simple algorithm to construct a realizer for $\mathcal{P}(1,2;n)$ whose cardinality is only an additive factor of at most $\frac{3}{2}$ away from the optimum.

preprint2020arXiv

New bounds on the Ramsey number $r(I_m, L_n)$

We investigate the Ramsey numbers $r(I_m, L_n)$ which is the minimal natural number $k$ such that every oriented graph on $k$ vertices contains either an independent set of size $m$ or a transitive tournament on $n$ vertices. Apart from the finitary combinatorial interest, these Ramsey numbers are of interest to set theorists since it is known that $r(ωm, n) = ωr(I_m, L_n)$ , where $ω$ is the lowest transfinite ordinal number, and $r(κm, n) = κr(I_m, L_n)$ for all initial ordinals $κ$ . Continuing the research by Bermond from 1974 who did show $r(I_3, L_3) = 9$ , we prove $r(I_4, L_3) = 15$ and $r(I_5, L_3) = 23$ . The upper bounds for both the estimates above are obtained by improving the upper bound of $m^2$ on $r(I_m, L_3)$ due to Larson and Mitchell (1997) to $m^2 - m + 3$ . Additionally, we provide asymptotic upper bounds on $r(I_m, L_n)$ for all $n \geq 3$ . In particular, we show that $r(I_m, L_3) \in Θ(m^2 / \log m)$ .

preprint2016arXiv

Track number of line graphs

The track number $τ(G)$ of a graph $G$ is the minimum number of interval graphs whose union is $G$ . We show that the track number of the line graph $L(G)$ of a triangle-free graph $G$ is at least $\lg \lg χ(G) + 1$ , where $χ(G)$ is the chromatic number of $G$ . Using this lower bound and two classical Ramsey-theoretic results from literature, we answer two questions posed by Milans, Stolee, and West [J. Combinatorics, 2015] (MSW15). First we show that the track number $τ(L(K_n))$ of the line graph of the complete graphs $K_n$ is at least $\lg\lg n - o(1)$ . This is asymptotically tight and it improves the bound of $Ω(\lg\lg n/ \lg\lg\lg n)$ in MSW15. Next we show that for a family of graphs $\mathcal{G}$ , $\{τ(L(G)):G \in \mathcal{G}\}$ is bounded if and only if $\{χ(G):G \in \mathcal{G}\}$ is bounded. This affirms a conjecture in MSW15. All our lower bounds apply even if one enlarges the covering family from the family of interval graphs to the family of chordal graphs.

preprint2015arXiv

Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes

A $d$ -hypertree on $[n]$ is a maximal acyclic $d$ -dimensional simplicial complex with full $(d-1)$ -skeleton on the vertex set $[n]$ . Alternatively, in the language of algebraic topology, it is a minimal $d$ -dimensional simplicial complex $T$ (assuming full $(d-1)$ -skeleton) such that $\tilde{H}_{d-1}(T;\mathbb{F})=0$ . The $d$ -hypertrees are a basic object in combinatorial theory of simplicial complexes. They have been studied; and yet, many of their structural aspects remain poorly understood. In this paper we study the boundaries $\partial_d T$ of $d$ -hypertrees, and the fundamental $d$ -cycles defined by them. Our findings include: 1. A full characterization of $\partial_d T$ over $\mathbb{F}_2$ for $d \leq 2$ , and some partial results for $d \geq 3$ . 2. Lower bounds on the maximum size of a largest simple $d$ -cycle on $[n]$ . In particular, for $d=2$ , we construct a {\em Hamiltonian $d$ -cycle} $H$ on $[n]$ , i.e., a simple $d$ -cycle of size ${{n-1} \choose d} + 1$ . For $d\geq 3$ , we construct a simple $d$ -cycle of size ${{n-1} \choose d} - O(n^{d-2})$ . 3. Observing that the maximum of the expected distance between two vertices chosen uniformly at random in a tree ( $1$ -hypertree) on $[n]$ is at most $\thicksim n/3$ , attained on Hamiltonian paths, we ask a similar question about $d$ -hypertrees. "How large can be the {\em average} size of a fundamental cycle of a $d$ -hypertree $T$ (i.e., the expected size of the dependency created by adding a $d$ -simplex on $[n]$ , chosen uniformly at random, to $T$ )?" For every $d \in \mathbb{N}$ , we construct an infinite family of $d$ -hypertrees $\{T\}$ with the average size of a fundamental cycle at least $c_d\, |T| \,=\, c_d\,{n-1 \choose d}$ , where $c_d$ is a constant depending on the dimension $d$ alone.

preprint2014arXiv

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl, in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl for 2-vertex-connected outerplanar graphs will work for all outer planar graphs.

preprint2014arXiv

Approximating the Cubicity of Trees

Cubicity of a graph $G$ is the smallest dimension $d$ , for which $G$ is a unit disc graph in ${\mathbb{R}}^d$ , under the $l^\infty$ metric, i.e. $G$ can be represented as an intersection graph of $d$ -dimensional (axis-parallel) unit hypercubes. We call such an intersection representation a $d$ -dimensional cube representation of $G$ . Computing cubicity is known to be inapproximable in polynomial time, within an $O(n^{1-ε})$ factor for any $ε>0$ , unless NP=ZPP. In this paper, we present a randomized algorithm that runs in polynomial time and computes cube representations of trees, of dimension within a constant factor of the optimum. It is also shown that the cubicity of trees can be approximated within a constant factor in deterministic polynomial time, if the cube representation is not required to be computed. As far as we know, this is the first constant factor approximation algorithm for computing the cubicity of trees. It is not yet clear whether computing the cubicity of trees is NP-hard or not.

preprint2014arXiv

Boxicity and separation dimension

A family $\mathcal{F}$ of permutations of the vertices of a hypergraph $H$ is called 'pairwise suitable' for $H$ if, for every pair of disjoint edges in $H$ , there exists a permutation in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for $H$ is called the 'separation dimension' of $H$ and is denoted by $π(H)$ . Equivalently, $π(H)$ is the smallest natural number $k$ so that the vertices of $H$ can be embedded in $\mathbb{R}^k$ such that any two disjoint edges of $H$ can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph $H$ is equal to the 'boxicity' of the line graph of $H$ . This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension.

preprint2014arXiv

Domination in designs

We commence the study of domination in the incidence graphs of combinatorial designs. Let $D$ be a combinatorial design and denote by $γ(D)$ the domination number of the incidence (Levy) graph of $D$ . We obtain a number of results about the domination numbers of various kinds of designs. For instance, a finite projective plane of order $n$ , which is a symmetric $(n^{2}+n+1,n+1,1)$ -design, has $γ=2n$ . %We also show that for any symmetric $(v,k,λ)$ -design it holds that $γ\leq 2k$ . We study at depth the domination numbers of Steiner systems and in particular of Steiner triple systems. We show that a $STS(v)$ has $γ\geq \frac{2}{3}v-1$ and also obtain a number of upper bounds. The tantalizing conjecture that all Steiner triple systems on $v$ vertices have the same domination number is proposed and is verified up to $v \leq 15$ . The structure of minimal dominating sets is also investigated, both for its own sake and as a tool in deriving lower bounds on $γ$ . Finally, a number of open questions are proposed.

preprint2014arXiv

On Additive Combinatorics of Permutations of \mathbb{Z}_n

Let $\mathbb{Z}_n$ denote the ring of integers modulo $n$ . In this paper we consider two extremal problems on permutations of $\mathbb{Z}_n$ , namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is not a permutation. Let the sizes be denoted by $s(n)$ and $t(n)$ respectively. The case when $n$ is even is trivial in both the cases, with $s(n)=1$ and $t(n)=n!$ . For $n$ odd, we prove $s(n)\geq (nϕ(n))/2^k$ where $k$ is the number of distinct prime divisors of $n$ . When $n$ is an odd prime we prove $s(n)\leq \frac{e^2}π n ((n-1)/e)^\frac{n-1}{2}$ . For the second problem, we prove $2^{(n-1)/2}.(\frac{n-1}{2})!\leq t(n)\leq 2^k.(n-1)!/ϕ(n)$ when $n$ is odd.

preprint2014arXiv

Partial list colouring of certain graphs

Let $G$ be a graph on $n$ vertices and let $\mathcal{L}_k$ be an arbitrary function that assigns each vertex in $G$ a list of $k$ colours. Then $G$ is $\mathcal{L}_k$ -list colourable if there exists a proper colouring of the vertices of $G$ such that every vertex is coloured with a colour from its own list. We say $G$ is $k$ -choosable if for every such function $\mathcal{L}_k$ , $G$ is $\mathcal{L}_k$ -list colourable. The minimum $k$ such that $G$ is $k$ -choosable is called the list chromatic number of $G$ and is denoted by $χ_L(G)$ . Let $χ_L(G) = s$ and let $t$ be a positive integer less than $s$ . The partial list colouring conjecture due to Albertson et al. \cite{albertson2000partial} states that for every $\mathcal{L}_t$ that maps the vertices of $G$ to $t$ -sized lists, there always exists an induced subgraph of $G$ of size at least $\frac{tn}{s}$ that is $\mathcal{L}_t$ -list colourable. In this paper we show that the partial list colouring conjecture holds true for certain classes of graphs like claw-free graphs, graphs with large chromatic number, chordless graphs, and series-parallel graphs. In the second part of the paper, we put forth a question which is a variant of the partial list colouring conjecture: does $G$ always contain an induced subgraph of size at least $\frac{tn}{s}$ that is $t$ -choosable? We show that the answer to this question is not always `yes' by explicitly constructing an infinite family of $3$ -choosable graphs where a largest induced $2$ -choosable subgraph of each graph in the family is of size at most $\frac{5n}{8}$ .

preprint2014arXiv

Rainbow Colouring of Split Graphs

A rainbow path in an edge coloured graph is a path in which no two edges are coloured the same. A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one rainbow path. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Between them, Chakraborty et al. [J. Comb. Optim., 2011] and Ananth et al. [FSTTCS, 2012] have shown that for every integer k, k \geq 2, it is NP-complete to decide whether a given graph can be rainbow coloured using k colours. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. Chandran and Rajendraprasad have shown that the problem of deciding whether a given split graph G can be rainbow coloured using 3 colours is NP-complete and further have described a linear time algorithm to rainbow colour any split graph using at most one colour more than the optimum [COCOON, 2012]. In this article, we settle the computational complexity of the problem on split graphs and thereby discover an interesting dichotomy. Specifically, we show that the problem of deciding whether a given split graph can be rainbow coloured using k colours is NP-complete for k \in {2,3}, but can be solved in polynomial time for all other values of k.

preprint2014arXiv

Separation dimension of bounded degree graphs

The 'separation dimension' of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $\mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $\mathcal{F}$ of total orders of the vertices of $G$ such that for any two disjoint edges of $G$ , there exists at least one total order in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $Θ(\log n)$ . In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree $d$ is at most $2^{9log^{\star} d} d$ . We also demonstrate that the above bound is nearly tight by showing that, for every $d$ , almost all $d$ -regular graphs have separation dimension at least $\lceil d/2\rceil$ .

preprint2014arXiv

Separation dimension of sparse graphs

The separation dimension of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $\mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $\mathcal{F}$ of permutations of the vertices of $G$ such that for any two disjoint edges of $G$ , there exists at least one permutation in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $Θ(\log n)$ . In this article, we focus on sparse graphs and show that the maximum separation dimension of a $k$ -degenerate graph on $n$ vertices is $O(k \log\log n)$ and that there exists a family of $2$ -degenerate graphs with separation dimension $Ω(\log\log n)$ . We also show that the separation dimension of the graph $G^{1/2}$ obtained by subdividing once every edge of another graph $G$ is at most $(1 + o(1)) \log\log χ(G)$ where $χ(G)$ is the chromatic number of the original graph.

preprint2014arXiv

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph $G$ is the minimum non-negative integer $k$ , such that $G$ can be represented as an intersection graph of axis-parallel $k$ -dimensional boxes (respectively $k$ -dimensional unit cubes) and is denoted by $box(G)$ (respectively $cub(G)$ ). It was shown by Adiga and Chandran (Journal of Graph Theory, 65(4), 2010) that for any graph $G$ , $cub(G) \le$ box $(G) \left \lceil \log_2 α\right \rceil$ , where $α= α(G)$ is the cardinality of the maximum independent set in $G$ . In this note we show that $cub(G) \le 2 \left \lceil \log_2 χ(G) \right \rceil box(G) + χ(G) \left \lceil \log_2 α(G) \right \rceil$ . In general, this result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we get, $cub(G) \le 2 (box(G) + \left \lceil \log_2 α(G) \right \rceil )$ . Moreover we show that for every positive integer $k$ , there exist graphs with chromatic number $k$ , such that for every $ε> 0$ , the value given by our upper bound is at most $(1+ε)$ times their cubicity. Thus, our upper bound is almost tight.

preprint2013arXiv

Boxicity and Cubicity of Product Graphs

The 'boxicity' ('cubicity') of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in $R^k$ . In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of $d$ , of the boxicity and the cubicity of the $d$ -th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the $d$ -th Cartesian power of any given finite graph is in $O(\log d / \log\log d)$ and $θ(d / \log d)$ , respectively. On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products.

preprint2012arXiv

Pairwise Suitable Family of Permutations and Boxicity

A family F of permutations of the vertices of a hypergraph H is called "pairwise suitable" for H if, for every pair of disjoint edges in H, there exists a permutation in F in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for H is called the "separation dimension" of H and is denoted by π(H). Equivalently, π(H) is the smallest natural number k so that the vertices of H can be embedded in R^k such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the "boxicity" of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension.

preprint2012arXiv

Product Dimension of Forests and Bounded Treewidth Graphs

The product dimension of a graph G is defined as the minimum natural number l such that G is an induced subgraph of a direct product of l complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and k-degenerate graphs. We show that every forest on n vertices has a product dimension at most 1.441logn+3. This improves the best known upper bound of 3logn for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a result on existence of orthogonal Latin squares to show that every graph on n vertices with a treewidth at most t has a product dimension at most (t+2)(logn+1). We also show that every k-degenerate graph on n vertices has a product dimension at most \ceil{8.317klogn}+1. This improves the upper bound of 32klogn for the same by Eaton and Rodl.

preprint2012arXiv

Rainbow Colouring of Split and Threshold Graphs

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k larger than 2, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

preprint2012arXiv

Rainbow Connection Number and Radius

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) <= r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (Star graph for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) <= rk. It is known that computing rc(G) is NP-Hard [Chakraborty et al., 2009]. Here, we present a (r+3)-factor approximation algorithm which runs in O(nm) time and a (d+3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r.

preprint2011arXiv

On Rainbow Connection Number and Connectivity

Rainbow connection number, $rc(G)$ , of a connected graph $G$ is the minimum number of colours needed to colour its edges, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we investigate the relationship of rainbow connection number with vertex and edge connectivity. It is already known that for a connected graph with minimum degree $δ$ , the rainbow connection number is upper bounded by $3n/(δ+ 1) + 3$ [Chandran et al., 2010]. This directly gives an upper bound of $3n/(λ+ 1) + 3$ and $3n/(κ+ 1) + 3$ for rainbow connection number where $λ$ and $κ$ , respectively, denote the edge and vertex connectivity of the graph. We show that the above bound in terms of edge connectivity is tight up-to additive constants and show that the bound in terms of vertex connectivity can be improved to $(2 + ε)n/κ+ 23/ ε^2$ , for any $ε> 0$ . We conjecture that rainbow connection number is upper bounded by $n/κ+ O(1)$ and show that it is true for $κ= 2$ . We also show that the conjecture is true for chordal graphs and graphs of girth at least 7.

preprint2011arXiv

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (Note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely cartesian product, lexicographic product and strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) <= 2r(G)+c, where r(G) denotes the radius of G and c \in {0,1,2}. In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [Basavaraju et. al, 2010]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight upto additive constants. The proofs are constructive and hence yield polynomial time (2 + 2/r(G))-factor approximation algorithms.

preprint2010arXiv

Rainbow Connection Number and Connected Dominating Sets

Rainbow connection number rc(G) of a connected graph G is the minimum number of colours needed to colour the edges of G, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we show that for every connected graph G, with minimum degree at least 2, the rainbow connection number is upper bounded by γ_c(G) + 2, where γ_c(G) is the connected domination number of G. Bounds of the form diameter(G) \leq rc(G) \leq diameter(G) + c, 1 \leq c \leq 4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, AT-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G) \leq 3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds. An extension of this idea to two-step dominating sets is used to show that for every connected graph on n vertices with minimum degree δ, the rainbow connection number is upper bounded by 3n/(δ + 1) + 3. This solves an open problem of Schiermeyer (2009), improving the previously best known bound of 20n/δ by Krivelevich and Yuster (2010). Moreover, this bound is seen to be tight up to additive factors by a construction of Caro et al. (2008).

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.

Deepak Rajendraprasad

Research overview

Is this your work?

27 publications

New bounds on the anti-Ramsey numbers of star graphs

Disjoint Total Dominating Sets in Near-Triangulations

A Note on Arc-Disjoint Cycles in Bipartite Tournaments

An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter

Characterization and a 2D Visualization of B $_0$ -VPG Cocomparability Graphs

Dimension of CPT posets

New bounds on the Ramsey number $r(I_m, L_n)$

Track number of line graphs

Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Approximating the Cubicity of Trees

Boxicity and separation dimension

Domination in designs

On Additive Combinatorics of Permutations of \mathbb{Z}_n

Partial list colouring of certain graphs

Rainbow Colouring of Split Graphs

Separation dimension of bounded degree graphs

Separation dimension of sparse graphs

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

Boxicity and Cubicity of Product Graphs

Pairwise Suitable Family of Permutations and Boxicity

Product Dimension of Forests and Bounded Treewidth Graphs

Rainbow Colouring of Split and Threshold Graphs

Rainbow Connection Number and Radius

On Rainbow Connection Number and Connectivity

Rainbow Connection Number of Graph Power and Graph Products

Rainbow Connection Number and Connected Dominating Sets

See the researcher in context

Building this map preview

Deepak Rajendraprasad

Research overview

Is this your work?

27 publications

New bounds on the anti-Ramsey numbers of star graphs

Disjoint Total Dominating Sets in Near-Triangulations

A Note on Arc-Disjoint Cycles in Bipartite Tournaments

An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter

Characterization and a 2D Visualization of B0_00​-VPG Cocomparability Graphs

Dimension of CPT posets

New bounds on the Ramsey number r(Im,Ln)r(I_m, L_n)r(Im​,Ln​)

Track number of line graphs

Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Approximating the Cubicity of Trees

Boxicity and separation dimension

Domination in designs

On Additive Combinatorics of Permutations of \mathbb{Z}_n

Partial list colouring of certain graphs

Rainbow Colouring of Split Graphs

Separation dimension of bounded degree graphs

Separation dimension of sparse graphs

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

Boxicity and Cubicity of Product Graphs

Pairwise Suitable Family of Permutations and Boxicity

Product Dimension of Forests and Bounded Treewidth Graphs

Rainbow Colouring of Split and Threshold Graphs

Rainbow Connection Number and Radius

On Rainbow Connection Number and Connectivity

Rainbow Connection Number of Graph Power and Graph Products

Rainbow Connection Number and Connected Dominating Sets

See the researcher in context

Building this map preview

Characterization and a 2D Visualization of B $_0$ -VPG Cocomparability Graphs

New bounds on the Ramsey number $r(I_m, L_n)$