ABSTRACT

A graph is a good way to illustrate some relations between things. But, not all relations can be illustrated by this graph. So, in this paper we will define a new type of graph, we call it a general-graph.

1. Introduction

Unlike other areas in mathematics, graph theory traces its beginning to definite time and place: the problem of the seven bridges of Königsberg, which was solved in 1736 by Leonhard Euler. And in 1752 we find Euler’s Theorem for planer graph. However, after this development, littlie was accomplished in this area for almost a century [1].

There are many physical systems whose performance depends not only on the characteristics of the components but also on the relative locations of the elements. An obvious example is an electrical network. One simple way of displaying a structure of a system is to draw a diagram consisting of points called vertices and line segments called edges which connect these vertices so that such vertices and edges indicate components and relationships between these components. Such a diagram is called linear graph. A graph G is a triple consisting of a vertex-set V(G), an edge-set E(G) and a relation that associated with each edge two vertices called its endpoints.

Definition 1. An oriented abstract graph is a pair (V, E) where V is finite non empty set of vertices and E is a set of ordered pairs of distinct elements of E with the property that if (v, w) Î E then (w, v) Ï E where the element (v, w) denote the edge from v to w [1,2].

Definition 2. An empty graph is a graph with no edges [1].

Definition 3. A multiple edges defined as two or more edges joining the same pair of vertices [3-7].

Definition 4. A loop is an edge joining a vertex to itself [3-7].

Definition 5. A simple graph is a graph with no loops or multiple edges [8,9].

Definition 6. A multiple graph is a graph with allows multiple edges and loops [3-7].

Definition 7. A complete graph is a graph in which every two distinct vertices are joined by exactly one edge [5,6,9,10].

Definition 8. A connected graph is a graph that in one piece, where as one which splits in to several pieces is disconnected [6].

Definition 9. Given a graph G, a graph H is called a subgraph of G if the vertices of H are vertices of G and the edges of H are edges of G [1,4,6].

Definition 10. Let v and w be two vertices of a graph. If v and w are joined by an edge, then v and w are said to be adjacent. Also, v and w are said to be incident with e then e is said to be incident with v and w [9].

Definition 11. Let G be a graph without loops, with nvertices labeled 1, 2, 3,···, n. and m edges labeled 1, 2, 3,···, m. The adjacency matrix A(G) is the n × n matrix in which the entry in row i and column j is the number of edges joining the vertices i and j [9].

Definition 12. Let G be a graph without loops, with nvertices labeled 1, 2, 3,···, n and m edges labeled 1, 2, 3,···, m. The incidence matrix I(G) is the nxm matrix in which the entry in row i and column j is l if vertex i is incident with edge j and 0 otherwise [9].

Definition 13. The degree of vertex v in a graph G, written, is the number of edges incident to v, except that each loop at v counts twice[11].

Definition 14. The order of a graph G, written, is the number of vertices in G [11].

Definition 15. The size of a graph G, written, is the number of edges in G [12].

2. The Main Results

In this article we will define a new type of graph which is generalization of the current graph. There exist some problems can not be illustrated by the classical graph, for example, the relation between students and their studied subjects, as shown in table below, the current graph does not illustrate this relation.

So we want to define a new type of graph illustrate this type of relations.

Before, introducing the definition of the new graph we will define a new types of edges.

Definition 1. The original edge is a discrete path between any two vertices, , denoted by, such that this path show the existence of the relation.

Definition 2. The inverse edge is an indiscrete path between any two vertices, , denoted by, such that this path show the existence of the inverse of given relation.

Definition 3. An inverse loop is an edge joining a vertex to itself and show the existence of the inverse of given relation.

Now we will define our new type of graph:

Definition 4. A general-graph G is a pair (V, E) where V is finite non empty set of vertices and E is a set of original edges and inverse edges.

A special cases of a general-graph will be introduced as follows:

Definition 5. An inverse-graph is a pair (V,) where V is finite non empty set of vertices and is a set of inverse edges.

Example 1. As shown in the following figure: the inverse-graph is a pair (V,) where

and.

Definition 6. An original-graph G is a pair (V, E) where V is finite non empty set of vertices and E is a set of original edges.

Now we will introduce types of a general-graph as follows:

Definition 7. An empty a general-graph is a general graph with vertices but the set E is empty.

Definition 8. A simple general-graph is a general-graph with no loops, no inverse loop and no multiple edges.

Definition 9. A multiple general-graph is a general-graph allows multiple edges.

Definition 10. A pseudo general-graph is a general-graph allowing edges to connect a vertex to itself.

Definition 11. A directed general-graph is a general-graph in which the set E is the set of ordered pairs of vertices.

Definition 12. A connected general graph is a general-graph that in one piece and the one which splits into several pieces is disconnected.

Definition 13. A complete general-graph is a general-graph in which every vertex is adjacent to every other vertex.

Definition 14. A complement general-graph of a general-graph G is a general-graph in which vertex set is the same and the edge set consists of all edges that are inverses of the edges in G.

Definition 15. A graph H is said to be supgraph of a general-graph, if and .

Proposition 1. A supgraph H of a general-graph G is a general-graph.

Definition 16. The order of a general-graph G, written, is the number of vertices in G.

Definition 17. The size of a general-graph G, written, is the number of edges in G.

Example 1. The order of a general-graph G, in definition 13, is and its size is.

Example 2. The order of a general-graph G, in definition 9, is and its size is.

Definition 18. Let be a general-graph, with nvertices labeled and m edges labeled,. The adjacency matrix is the n × n matrix in which the entry in row i and column j is the number of edges joining the vertices i and j, i.e. m means the number of original edges joining the vertices i and j is m, –m means the number of inverse edges joining the vertices i and j is m and (m)(–n) means the number of original edges joining the vertices i and j is m and means the number of inverse edges joining the vertices i and j is n.

Definition 19. Let be a general-graph, with nvertices labeled and m edges labeled . The incidence matrix is the n × m matrix in which the entry in row i and column j is l if vertex i is incident with edge j or –1 if vertex i is incident with inverse edge j and 0 otherwise.

Example 1. The adjacency matrix and the incidence matrix of a general-graph as shown in definition 13 are given by

Example 2. The adjacency matrix and the incidence matrix of a general-graph as shown in the following figure are given by

Definition 20. A general-graph G is bipartite if its vertex set can be partitioned into two sets X and Y in such a way that every edge (original edge or inverse edge) of G has one end vertex in X and the other in Y, X and Y are called the partite sets.

Example 3. In figure blow the first two graphs are bipartite but the third graph is not bipartite because it is not possible to partition the vertices into two such sets.

Definition 21. A bipartite general-graph G with partite sets X and Y is called complete bipartite general-graph if its edge set is of the form. That is, if every possible connection of a vertex of X with a vertex of Y is present in the graph. Such a graph is denoted by.

3. Acknowledgements

The authors are deeply indebted to the team work at the deanship of the scientific research—Taibah University for their valuable help and critical guidance and for facilitating many administrative procedures. This research work was financed supported by Grant no. 226/1432 from the deanship of the scientific research at Taibah University, Al-Madinah Al-Munawwarah, Saudi Arabia

REFERENCES

NOTES

^*Corresponding author.