Show simple item record

dc.contributor.advisorChandran, L Sunil
dc.contributor.authorRajendraprasad, Deepak
dc.date.accessioned2018-04-05T03:05:56Z
dc.date.accessioned2018-07-31T04:39:03Z
dc.date.available2018-04-05T03:05:56Z
dc.date.available2018-07-31T04:39:03Z
dc.date.issued2018-04-05
dc.date.submitted2013
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/3336
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/4201/G25730-Abs.pdfen_US
dc.description.abstractThis thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices is connected by atleast one path in which no two edges are coloured the same. The rainbow connection number of a graph is the minimum number of colours required to rainbow colour it. In this thesis we give upper bounds on rainbow connection number based on graph invariants like minimum degree, vertex connectivity, and radius. We also give some computational complexity results for special graph classes. Product dimension The product dimension or Prague dimension of a graph G is the smallest natural number k such that G is an induced subgraph of a direct product of k complete graphs. In this thesis, we give upper bounds on the product dimension for forests, bounded tree width graphs and graphs of bounded degeneracy. Boxicity and cubicity The boxicity (cubicity of a graph G is the smallest natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes(axis-parallel unit cubes) in Rk .In this thesis, we study the boxicity and the cubicity of Cartesian, strong and direct products of graphs and give estimates on the boxicity and the cubicity of a product graph based on invariants of the component graphs. Separation dimension The separation dimension of a hypergraph H is the smallest natural number k for which the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyper plane normal to one of the axes. While studying the boxicity of line graphs, we noticed that a box representation of the line graph of a hypergraph has a nice geometric interpretation. Hence we introduced this new parameter and did an extensive study of the same.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG25730en_US
dc.subjectGraph Theoryen_US
dc.subjectRainbow Coloring - Graphsen_US
dc.subjectProduct Dimension - Graphsen_US
dc.subjectBoxicityen_US
dc.subjectCubicityen_US
dc.subjectHypergraphsen_US
dc.subjectProduct Graphsen_US
dc.subjectForests Graphsen_US
dc.subjectTreewidth Graphsen_US
dc.subjectTree (Graph Theory)en_US
dc.subjectSplit Graphsen_US
dc.subjectThreshold Graphsen_US
dc.subjectGraph - Coloringen_US
dc.subjectRainbow Connectionen_US
dc.subject.classificationComputer Scienceen_US
dc.titleRainbow Colouring and Some Dimensional Problems in Graph Theoryen_US
dc.typeThesisen_US
dc.degree.namePhDen_US
dc.degree.levelDoctoralen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record