L. Sunil Chandran
Cubicity, Degeneracy, and Crossing Number.
Fri, 05/27/2011 - 15:01 — SomNambulAuthors: L. Sunil Chandran, Rogers Mathew, Abhijin Adiga
Subjects: Combinatorics
AbstractA $k$-box $B=(R_1,R_2,...,R_k)$, where each $R_i$ is a closed interval on the
real line, is defined to be the Cartesian product $R_1\times R_2\times...\times
R_k$. If each $R_i$ is a unit length interval, we call $B$ a $k$-cube.
\emph{Boxicity} of a graph $G$, denoted as $\boxi(G)$, is the minimum integer
$k$ such that $G$ is an intersection graph of $k$-boxes. Similarly, the
\emph{cubicity} of $G$, denoted as $\cubi(G)$, is the minimum integer $k$ such
that $G$ is an intersection graph of $k$-cubes.Rainbow Connection Number and Radius.
Wed, 11/03/2010 - 16:01 — SomNambulAuthors: L. Sunil Chandran, Manu Basavaraju, Deepak Rajendraprasad, Arunselvan Ramaswamy
Subjects: Combinatorics
AbstractRainbow 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 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.Boxicity of Line Graphs.
Fri, 09/24/2010 - 15:01 — SomNambulAuthors: L. Sunil Chandran, Rogers Mathew, Naveen Sivadasan
Subjects: Combinatorics
AbstractBoxicity of a graph H, denoted by box(H), is the minimum integer k such that
H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this
paper, we show that for a line graph G of a multigraph, box(G) <=
2\Delta(\lceil log_2(log_2(\Delta)) \rceil + 3) + 1, where \Delta denotes the
maximum degree of G. Since \Delta <= 2(\chi - 1), for any line graph G with
chromatic number \chi, box(G) = O(\chi log_2(log_2(\chi))). For the
d-dimensional hypercube H_d, we prove that box(H_d) >= (\lceil log_2(log_2(d))
\rceil + 1)/2.Acyclic Edge Coloring of Triangle Free Planar Graphs.
Thu, 07/15/2010 - 15:01 — SomNambulAuthors: L. Sunil Chandran, Manu Basavaraju
Subjects: Discrete Mathematics
AbstractAn $acyclic$ edge coloring of a graph is a proper edge coloring such that
there are no bichromatic cycles. The \emph{acyclic chromatic index} of a graph
is the minimum number k such that there is an acyclic edge coloring using k
colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks
(and much earlier by Fiamcik) that $a'(G)\le \Delta+2$, where $\Delta
=\Delta(G)$ denotes the maximum degree of the graph.On the SIG dimension of trees under $L_{\infty}$ metric.
Thu, 10/29/2009 - 16:01 — SomNambulAuthors: L. Sunil Chandran, Rajesh Chitnis, Ramanjit Kumar
Subjects: Combinatorics
AbstractWe study the $SIG$ dimension of trees under $L_{\infty}$ metric and answer an
open problem posed by Michael and Quint (Discrete applied Mathematics: 127,
pages 447-460, 2003). Let $T$ be a tree with atleast two vertices. For each
$v\in V(T)$, let leaf-degree$(v)$ denote the number of neighbours of $v$ that
are leaves. We define the maximum leaf-degree as $\alpha(T) = \max_{x \in
V(T)}$ leaf-degree$(x)$. Let $S = \{v\in V(T) |$ leaf-degree$(v) = \alpha\}$.
If $|S| = 1$, we define $\beta(T) = \alpha(T) - 1$. Otherwise define $\beta(T)
= \alpha(T)$.
User login
