A Study on Graph and Its Approaches

It has become a tradition to describe graphs by means of diagrams in which each element of the vertex set of the graph is represented by a dot and an edge e = uv is represented by a curve joining the dots that represent the vertices u and v. A parameter that appears often when studying graphs is the degree of vertex. The degree of a vertex u of a graph G, denoted by deg G, or simply by deg u or d(u), if the graph G is clear from the context, is defined as d(u) = | {v/uv 2 E(G)} |. A vertex v of a graph G is called even, if its degree is even and odd, if its degree is odd. Also, if deg v = 0, v is called an isolated vertex, and if deg v = 1, it is called an end vertex. Also, if e = uv is an edge of a graph G such that either deg u = 1 or deg v = 1, then e is called a pendant edge of G. Two graphs are said to be isomorphic if they have the same structure, and at the most, they differ in the way their vertices and edges are labeled, or in the way they are drawn. The complement G of a graph G has V(G) as its vertex set, but two vertices are adjacent in G if and only if they are not adjacent in G. A graph and its complement are shown in Figure. The graphs Kp are called totally disconnected, and are regular of degree 0. A self-complementary graph is one which is isomorphic to its complement. A self-complementary graph is shown in Figure . We also discuss here those operations on graphs that are used in this thesis. In all the definitions follows, we assume that, graphs G1 and G2 have disjoint vertex sets V1 and V2 and their edge sets as E1 and E2 respectively. The union of G1 and G2, denoted as G = G1 E G2 has V = V1 E V2 and E = E1 [ E2. Join of G1 and G2, as defined by Zykov [31], denoted G1+G2, the vertex set consists of V = V (G1)[V (G2) and the edge set, all edges obtained by joining V1 with V2. In particular, Km,n = Km + Kn. different from Gj for i 6= j. To define the cartesian product G1 × G2, consider any two vertices u = (u1, u2) and v = (v1, v2) in V = V1 × V2. Then u and v are adjacent in G1 × G2 whenever u1 = v1 and u2v2 2 E(G2) or u2 = v2 and u1v1 2 E(G1). The cartesian product of G1 = P2 and G2 =P2 is shown in Figure . Let graph G has at least one edge. The line graph L(G) of G, has E(G) as its vertex set with two vertices of L(G) are adjacent whenever the corresponding edges of G are adjacent. The line graph of K4 is shown in Figure . We write L2(G) = L(L(G)), and in general Ln(G) = L(Ln−1(G)). The distance d(u, v) between two vertices u and v in G is the minimum length of a path joining them if any; otherwise d(u, v) = 1. A shortest u−v path is called a u−v geodesic. The diameter d(G) of a connected graph G is the length of any longest geodesic.

A classical subject of metric graph theory that are related to geometric questions are that of distance regular graphs which are intimately related with combinatorial designs and finite geometries. The study of low-distortion embeddings of graphs and finite matric spaces into l2 or l1 spaces with numerous applications in the design of approximation algorithms was initiated by Lineal et.al. . In the mathematical field of graph theory, the hypercube Qn is a regular graph with 2n vertices, which corresponds to the subsets of a set with n elements. Two vertices labeled by subsets W and B are joined by an edge if and only if W can be obtained from B by adding or removing a single element. Geometric representations of graphs have been much studied for the insight they provide into the graph algorithms, graph structure, and graph visualization. Linial et.al. considered the following representation in the graph is equal to the L1-distance between their coordinates? They (Linial et.al. ) called the minimum possible dimension d of such an embedding (if one exists), the lattice dimension of the graph, and shown that the lattice dimension of any lattice-embeddable graph may be found in polynomial time. It is also shown that the lattice dimension of any tree is exactly dl2 e, where l denotes the number of leaves of the tree. Any l-length path can be viewed as a sub-graph of the hypercube {0, 1}l by mapping its vertices to the points where superscripting stands for repetition of coordinates. Similarly, finite portions of the integer lattice can be mapped isometrically to a hypercube {0, 1}dl, by applying the above embedding separately to each lattice coordinate. The graphs with finite lattice dimension are exactly the isometric hypercube sub-graphs, also known as partial cubes. The partial cube representation of a graph is unique up to cube symmetries and, a polynomial time algorithm for finding such representations is known from the work of Djokovic . Partial cubes arise naturally as the state transition graphs of media, systems of states and state transitions studied by Falmagne et. al., that arise in political choice theory and that can also be used to represent many familiar geometric and combinatorial systems such as hyper-plane arrangements. The integer lattice can be viewed as a Cartesian product of paths; instead, one could consider products of other graphs. Thus, for instance, one could similarly define the tree dimension of a graph to be the minimum k such that the graph has an isometric embedding into a product of k trees. The graphs with finite tree dimension are again just the partial cubes. Chepoi et. al. showed that, certain graph families have bounded tree dimension, and used the corresponding product representations as a data structure to answer distance queries in these graphs. Recognizing graphs with tree dimension k is polynomial for k = 2 , but NP-complete for any k > 2 . Let (Vn, d) be a distance space where d is rational valued. Then, (Vn, d) is l1-embeddable if and only if (Vn, d) is hypercube embeddable for some scalar. Let d be a distance on Vn that is embeddable and takes rational values. Every integer for which (Vn, d) is hypercube embeddable is called a scale of (Vn, d). They [12] also called d is hypercube embeddable with scale . The smallest such integer is called the minimum scale of (Vn, d) and is denoted by d. Deza et.al also established the following Lemma. There exists an integer such that d is hypercube embeddable for every embeddable distance d on Vn that is an integer valued. Deza et.al also initiated to study the graphs whose path metric admits some

embeddable. Similarly, a graph G is called a hypercube embeddable graph, if its path metric dG is isometrically hypercube-embeddable. Equivalently, a graph G is said to be hypercube embeddable if its vertices can be labelled with the Hamming distance between their labels.

A graph G = (V,E) is called a bitopological graph if there exist a set X and a set-indexer f on G such that both f(V ) and f_(E) [ ; are topologies on X. The corresponding set-indexer is called a bitopological set-indexer of G. We prove the existence of bitopological set-indexer. We give a characterization of bitopological complete graphs. We define equi-bitopological graphs and establish certain results on equi-bitopological graphs. We identify certain classes of graphs, which are bitopological and define bitopological index (G) of a finite graph G as the minimum cardinality of the underlying set X. Given a graph G = (V,E), we can relate it to different topological structures. In 1967, J. W. Evans et.al conceived this idea and he proved that there is a one to one correspondence between the set of all topologies on a set X with n points and the set of all transitive digraphs with n points. He established his results as follows. Let V be a finite set and T be a topology on V . The transitive digraph corresponding to this topology is got by drawing a line from u to v, if and only if, u is in every open set containing v. Conversely let D be a transitive digraph on V ; the family B = {Q(a) : a E V } forms a base for a topology on V , where Q(a) = {a} [ {b E V : (b, a) E E(D)}. In 1968 T.N. Bhargav and T.J. Ahlborn analysed the topological spaces associated with digraphs. According to them a subset A of V (D) is open if and only if for every pair of points i, j E V with j in A and i not in A, (i, j) is not a line in D. Sampathkumar [15] extended this results to the case in which the point set is infinite. Sampathkumar et.al [16] also investigated the topological spaces associated with signed graphs and semigraphs. Let S = (V,E) be a signed graph. A subset A of V is an open set in the positive E-topology on S denoted by S if and only if u E A, uv E E+(S) implies that v E A. Similarly he defined negative E-topology (S). He defined the topology V on the vertex set V (D) of a disemigraph D = (V,E) as follows: A subset S of V (D) is open whenever u E S and v E V (D) such that vu is a partial arc, then v E S. Hypergraph theory is something different and much more generalized concept of graph theory. Given a set V of vertices, an edge of a simple graph on V is a set of two vertices, while an edge of a hypergraph on V is any subset of V . The theory of hypergraphs suitable formulation of the theorems for hypergraphs in such a way that they contain the graph as a special case. Chromatic index of the hypergraph H of dcsl-graph K1,7 is eight, equal to the degree of H. Thus, we strongly believe that the hypergraphs of dcsl-graphs are graphs which satisfy the coloured edge property. In general, a hypergraph and its dual hypergraph need not be isomorphic. But it happens in the case of 1-uniform di-graphs. It is interesting to note that, if (G, f) is a 1-uniform di-graph then, the hypergraph Hf G and the dual hypergraph of Hf G are isomorphic. Figure give the hypergraph corresponding to 1-uniform path P6 and Figure depicts its dual graph. Note that the hypergraphs in Figure

The theory of isometric set-labeling are rich in theory, with many applications. The main motivation to study isometric set-labeling is due to the problem in communication theory posed by Pierce in 1972. In a telephone network one wishes to be able to establish a connection between two terminals A and B without B knowing that a message is on its way. The idea is to let the message be proceeded by some ´address’ of B, permitting to decide at each node of the network in which direction the message should proceed. The constants of proportionality. The most natural way of devising such a scheme is by labeling the nodes by strings of subsets of a set X, which amounts to try to embed the graph in a dcsl-graph. Interesting problems and conjectures are identified in both the dcslgraphs, bitopological graphs and hypergraph representation of dcslgraphs. They are already pointed out in the respective chapters. However, we list below some of the most important problems which are open for further research and investigation. Problem 1. Characterize a dispersible dcsl-graph. Problem 2. Consider any structure-activity relationship R of a molecular graph that has been identified to be well correlated with the Weiner index. Is it possible to achieve such a correlation using MWeiner index for a low cardinality dcsl-sets X as possible? Problem 3. For any dcsl-graph G, the dispersivity of (G) of G is the least cardinality of a ground set X, such that G admits a dispersive dcsl. Also, find Kn. Problem 4. Find the necessary condition for a graph to be l1-embeddable, k-uniform dcsl-graph.

• B.D. Acharya, Set-valuations of Graphs and Their Applications, MRI Lecture Notes in Applied Mathematics, No.2, Mehta Research Institute of Mathematics and Mathematical Physics, Allahabad.

• B.D. Acharya, Set-indexers of a graph and set-graceful graphs, Bull. Allahabad Math. Soc., 16(2001), 1-23.

• B.D. Acharya, Contributions to the Theories of Graphs, Graphoids and Hypergraphs, The Indian Institute of Technology.

• B.D. Acharya, M. Lasvergnas, Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality, J. Combin. Theory. B.33 52-56.

• C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam.

• C. Berge, Hypergraphs: Combinatorics of Finite Sets, North-Holland, Amsterdam.

• M. Buratti, G. Burosch and P.V. Ceccherint, A characterization of hypergraphs which are products of a finite number of edges, Rendiconti di Matematica, Serie VII Volume 17, Roma (1997), 373−385.

• E. Sampathkumar and L. Pushpalata, Eulerian Hypergraph, Advanced Studies in Contemporary Mathematics, 8(2004), 115−119.

• J. Sedlaˇcek, Some properties of magic graphs, in: Graphs, Hypergraphs and Block Systems, Proc. Conf. Held in Zielona Gora , 247 -253.

 M. Sonntag, Hanns-Martin Teichert, Competition hypergraphs, Discrete Applied Mathematics 324 − 329.