1.	Abstract

Mathematica contains a large collection of functions for computing in many areas, such as numerics, symbolics, and graphics. webMathematica makes all of these functionality avaliable over the web. The use of Mathematica  in Graph Theory, which is also part of Discrete Mathematics, has been extensively explained by Steven Skiena. In this paper, we consider many classes of graphs, how to color and construct them and also we introduce the cycle structure in graphs with webMathematica by using the Combinatorica package.

2.	Introduction

3.	Graph Coloring with webMathematica

Graph theory would not be what it is today if there had been no coloring problems. In fact, a major portion of the 20th-century research in graph theory has its origin in the four color problem. Proper coloring of a graph is an assignment of colors either to the vertices of the graphs, or to the edges, in such a way that adjacent vertices / edges are colored differently. In this chapter, we introduced some modules and used Combinatorica package to color the vertices and the edges of the graphs with webMathematica. First we should give some definitions of common graphs then we will give the webMathematica commands. In order to run these commands webMathematica should be installed.  [Ufuktepe 2003]

A complete graph is a simple graph such that every pair of vertices is joined by an edge. A nontrivial closed path is called a cycle. A graph which is obtained by joining a new vertex to every vertices of a cycle is called a wheel. A connected acyclic graph is called a tree.

3.1 Vertex Coloring

The most applications involving vertex coloring are concerned with determining the minimum number of colors required under the condition that the end points of an edge cannot have the same color. A proper vertex  coloring of a graph is an assignment from its vertex set to a color set that the end points of each edge are assigned two different colors. The chromatic number of a graph G, denoted by χ(G), is the minimum number of different colors required for a proper vertex coloring of G.
Applications of vertex coloring include scheduling, assingment of radio frequencies, seperating combustible chemical combinations, and computer optimization. We use some commands in the Combinatorica package with Mathematica to color the vertices of graphs and to give web-based examples with webMathematica as follows:

Needs["MSP`"]

<< DiscreteMath`Combinatorica`

ColorVertices[g_] := 
      Module[{c, p, s}, 
c = 
          VertexColoring[g]; 
p = 
          Table[Flatten[Position[c, i]], {i, 1, 
              Max[c]}]; 
s = 
          MSPShow[ShowGraph[Highlight[g, p]]]]

$$n =  
        Input["Enter the number of the vertices of your graph"];
g = CompleteGraph[$$n];
ColorVertices[g]

If we change the CompleteGraph[n] by Cycle[n] , Wheel[n], Star[n] and RandomTree[n], we can also color these graphs.

3.2 Edge Coloring

Edge coloring is an optimization problem: Given a graph, how many colors are required to color its edges in such a way that no two edges which share an
endpoint receive the same color? The required number of colors is called the chromatic index of G and is denoted by χ' (G). We use some commands in the Combinatorica package with Mathematica to color the edges of graphs and to give web-based examples with webMathematica as follows:

ColorEdges[h_] := 
      Module[{k, e, m, kk, r, s}, 
k = 
          EdgeColoring[h]; 
e = 
          Edges[h]; 
m = Max[k]; 
kk = 
          Table[i, {i, 1, 1000}]; 
r = 
          For[i = 1, i <= m, 
            For[j = 1, j <= M[h], 
              If[k[[j]] == i, 
                kk[[j]] = 
                  Hue[i/m]]; j++]; i++]; 
s = 
          MSPShow[ShowGraph[h, 
              Table[{e[[i]], EdgeColor -> kk[[i]]}, {i, 1, 
                  M[h]}], 
VertexNumber -> On,  
              EdgeStyle -> Thick]]]

$$b = 
        Input["Enter the number of the vertices of your graph"];
h = Wheel[$$b];
ColorEdges[h]

If we change the  Wheel[n] by CompleteGraph[n], Cycle[n], Star[n] and RandomTree[n], we can also color these graphs.

4.	Generating graphs with webMathematica

The most important operations on graphs are sum, union, join, and product of two graphs. We will do these operations with the common graphs; complete graph, random tree, wheel, and cycle.

The union of two graphs is formed by taking the union of the vertices and edges of the graphs.Thus the union of graphs is always disconnected.To take the union of two graphs we enter the number of the graphs we choose and their vertex numbers into the boxes then we see the union of those graphs and also its proper vertex coloring. For the complete graph the user should enter "1", for random tree "2", for wheel "3", for cycle "4".

$$a = 
        Input["Enter the number of the first graph you chose"];
$$b = 
        Input["Enter the number of the vertices of that graph"];
$$c = 
        Input["Enter the number of the second graph you chose"];
$$d = 
        Input["Enter the number of the vertices of that graph"];
Which[$$a == 
        1 ,  g1 = CompleteGraph[$$b];, 
$$a == 
        2,  g1 = RandomTree[$$b];, 
$$a == 
        3, g1 = Wheel[$$b];, 
$$a == 
        4, g1 = Cycle[$$b];]
Which[$$c == 
        1 ,  g2 = CompleteGraph[$$d];, 
$$c == 
        2,  g2 = RandomTree[$$d];, 
$$c == 
        3, g2 = Wheel[$$d];, 
$$c == 
        4, g2 = Cycle[$$d];]
MSPShow[ShowGraph[GraphUnion[g1, g2]]]

This script above can be extended for the other graph operations: sum, join and product by switching GraphUnion with GraphSum, GraphJoin or GraphProduct .

The sum operation of two graphs is to take the edges of the second graph and add them to the first graph.
The join of two graphs is their union with the addition of edges between all pairs of vertices from different graphs.
The product of two graphs G x H has a vertex set defined by the Cartesian product of the vertex sets of G and H. There is an edge between (u,v) and (s,t) if u=s and v is adjacent to t in H or v=t and u is adjacent to s in G.

5.	Cycle structure in graphs with webMathematica

\(A\ cycle\ in\ a\ graph\ is\ a\ simple\ closed\ path . \ 
            We\ will\ represent\ a\ cycle\ in\ G\ as\ a\ list\ of\ vertices\ C = v\_1, v\_2,  ... , 
      v\_1\ such\ that\ there\ is\ an\ edge\ of\ G\ from\ each\ vertex\ to\ the\ next\ in\ \(\(G\)\(.\)\)\)

5.1 Eulerian Cycles

Euler initiated the study of graph theory in 1736 with the famous Seven Bridges of Königsberg problem. The town of Königsberg straddled the Pregel River with a total of seven bridges connecting the two shores and two islands. The townsfolk were interested in crossing every bridge exactly once and returning to the starting point. Euler proved that this was impossible. More generally, he proved that a tour of all edges without repetition in a connected, undirected graph is possible if and only if each 
vertex is of even degree. Such graphs are known as Eulerian Graphs. An Eulerian cycle is a complete  tour of all the edges of a graph. The term circuit is often used instead of cycle, since each vertex can be visited more than once.

We use some commands in the Combinatorica package with Mathematica to find the Eulerian cycle and to give web-based examples with webMathematica. If you enter the number of the vertices you can see the Eulerian cycle in that graph if there exist. In the script below, this is done for the Cycle with the odd number of vertices.

<< Graphics`Animation`

\(GEuler[x_Graph]\  := \ 
        Module[{\ data\  = \ x, \ el}, \ eulerList\  = \ EulerianCycle[x]; \ 
          el\  = \ Partition[eulerList, \ 2, \ 
              1]; \ 
data\  = 
            SetGraphOptions[\ 
              data, \ {\ eulerList[\([1]\)], \ 
                VertexColor -> 
                  Green}]; 
eulerfile\  = \ 
            Table[Show[\ 
                Graphics[\ {Rectangle[\ {0, 0}, \ {0.8, \ 
                        0.8}, 
MSPShow[
                        ShowGraph[\ 
                          Highlight[\ 
                            data, \ {Take[el, \ Quotient[t, \ 2]], \ {\ 
                                eulerList[\([\ 
                                    Quotient[t, \ 2]\  + \ 
                                      Mod[t, \ 
                                        2]]\)]\ }\ }, \ {HighlightedEdgeColors\  -> \ {Blue}, \ 
                              HighlightedVertexColors\  -> \ {Yellow}, \ 
                              HighlightedVertexStyle\  -> \ Disk[Normal]}], \ 
                          PlotLabel\  -> \ "Eulerian Cycle", \ 
                          TextStyle\  -> \ {FontSize\  -> \ 15, \ 
                              FontColor -> 
                                Purple}, 
Background -> RGBColor[1, 1, 1], \ Graphics\ ]]], 
\ 
                    Text["www.combinatorica.com", \ {0.5, 
                        0.0}, \ {TextStyle -> {FontColor -> 
                              Red}}]\ }, 
{\ 
                    ImageSize -> 350, \ 
                    AspectRatio -> 1}\ ]], \ {t, \ 1, \ 
                2*\((Length[eulerList]\  - \ 1)\), \ 
                1}]; \ 
eulerfile]\)

$$n = 
        Input["Enter the number of the vertices"];
g = Cycle[n];
MSPShowAnimation[GEuler[g]]

5.2 Hamiltonian Cycles

A Hamiltonian cycle of a graph G is a cycle which visits every vertex in G exactly once, as opposed to an Eulerian cycle which visits each edge exactly once. A Hamiltonian path is like a Hamiltonian cycle, except that it is a path. The problem of computing a Hamiltonian cycle or a Hamiltonian path is fundamentally different from the problem of computing an Eulerian cycle, because testing whether a graph is Hamiltonian is NP-complete.

We use some commands in the Combinatorica package with Mathematica to find the Hamiltonian cycle and to give web-based examples with webMathematica. If you enter the number of the vertices you can see the Hamiltonian cycle in that graph if there exist. In the script below, this is done for the Wheel.

Clear[x, g, n]

Ham[x_Graph]  :=  
      Module[{hamfile,  data  =  x,  el}, 
 
        hamList  =  HamiltonianCycle[x,  1];  
        el  =  Partition[hamList,  2,  1]; 
 
        hamfile  =  
          Table[ Graphics[ {Rectangle[ {0, 0},  {0.8,  
                    0.8}, 
MSPShow[
                    ShowGraph[ 
                      Highlight[ 
                        x,  {Take[el,  
                            Quotient[t,  2]], 
 
                          Take[hamList,  
                            Quotient[t,  2]  +  
                              Mod[t,  
                                2]]},  {HighlightedEdgeColors  ->  {Red},  HighlightedVertexColors  ->  {Black},  
                          HighlightedVertexStyle  ->  
                            Disk[Normal]}],    Graphics ]]] }, 
{ ImageSize -> 350,  
                AspectRatio -> 1}],  {t,  1,  
              2*(Length[hamList]  -  1),  1}];  hamfile]

$$n = 
        Input["Enter the number of the vertices"];
g = Wheel[n];
MSPShowAnimation[Ham[g]]

6.	References