This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These ...

Over the past decade, the explosive growth of the Internet has led to a surge of interest to understand and predict aggregate behavior of large number of people or agents, particularly when they are connected through an ...

A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called ...

This 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 ...

In this thesis we study the following dimensional parameters : boxicity, cubicity, threshold dimension and poset dimension. While the first three parameters are defined on graphs, poset dimension is defined on partially ...

The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following ...

The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. ...

In this thesis we study the isoperimetric problem on trees and graphs with bounded treewidth. Let G = (V,E) be a finite, simple and undirected graph. For let δ(S,G)= {(u,v) ε E : u ε S and v ε V – S }be the edge boundary ...

Conjectured in 1943, Hadwiger’s conjecture is one of the most challenging open problems in graph theory. Hadwiger’s conjecture states that if the chromatic number of a graph G is k, then G has a clique minor of size at ...

Social networks are an inseparable part of human lives, and play a major role in a wide range of activities in our day-to-day as well as long-term lives. The rapid growth of online social networks has enabled people to ...