Mathematics Graph Theory & Modern Algebra

The theory of graphs looks at the graph-related structure, properties and algorithms. Graphs represent several equivalents; the principal concept, a norm that is adopted also in this paper, is one representation in particular. A graph, denoted G, is defined as an ordered pair composed of two distinct sets: 1. A set of vertices, denoted V (G) 2. A set of edges, denoted E(G) The order of a graph G refers to |V (G)| and the size of a graph G refers to |E(G)|. This is to say, the number of vertices is indicated in order, and the sum of borders is indicated. We use matrices as an extremely useful alternative representation to perform calculations with these graphs. The event, adjacence, size, and Laplacian matrices contain these representations. In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E)}G=(V,E) comprising: V, a set of vertices (also called nodes or points); a set of edges (also called links or lines), which are unordered vertical pairs (that is, two distinct vertices are connected with the edge). This type of object can be called an undirected simple graph precisely to avoid confusion. In the edge the vertices and are called the endpoints of the edge. The edge is said to join and to be incident on . Within a graph there can be a edge and not a surface. The two or more edges that connect the same two vertices are multiple edges that are not permitted by the definition above. In one more general sense of the term allowing multiple edges, [3][4] a graph is an ordered triple comprising: V, a set of vertices (also called nodes or points); E, a set of edges (also called links or lines); An Incidence function that maps each edge into an unordered vertical pair (i.e. a two-edge edge). This sort of object should specifically be called an undirected multigraph in order to prevent confusion.

A loop is a rim that connects to itself a hinge. Graphs as specified in the two definitions above cannot have loops since the loop that attaches a vertex x to itself is either the edge (in case of a simple undirected graph) or on (in the case of an undirected multigraph).. So to allow loops the definitions must be expanded. For undirected simple graphs, the definition of should be modified to . For undirected multigraph, the definition of should be modified to . To prevent confusion, undirected simple graphs allowing loops and undirected multigraph allowing loops can be called these kinds of artifacts, respectively. Generally, they are taken as finite and many of the most common results for infinite graphs are not valid (or different), since in the infinite case, many arguments fail. In addition, V is often believed not to be vacant but E may be vacant. The graph |V| sequence is its vertical number. The graph’s |E| size is and its edge number. The degree or valence of the vertex is the number of edges, where a loop is double counted.

A directed graph or digraph is a graph in which edges have orientations. In one restricted but very common sense of the term,[5] a directed graph is an ordered pair G=(V,E) comprising: V, a set of vertices (also called nodes or points); A set of edges, or pairs of vertices, which are ordered (i.e., an edge is connected to two distinctive vertices), (which also means guiding boundaries, directed lines, arrows, or arcs). To avoid ambiguity, this type of object may be called precisely a directed simple graph. The endpoints x and y of the surface of the surface, x the tail of the bottom, and y the head of the rim are not a surface. The surface (y, x) is known as the inverted surface (x, y). Multiple edges are two or more edges with the same tail and one ear, not permitted by the above definition.

In one more general sense of the term allowing multiple edges,[5] a directed graph is an ordered triple comprising: V, a set of vertices (also called nodes or points); E, a set of edges (also called directed edges, directed links, directed lines, arrows or arcs); An incidence function that maps each edge to a sequenced pair of vertices (the edge with two different vertices is associated). A guided multigraph can be specifically named this type of object to avoid ambiguity. A loop is an edge that connects to itself a hinge. Directed graphs as described in the above two definitions cannot have loops, as a loop that joins an umbrella x is either the edge (for the simple diagram directed) or an incident (for the directed multi graph) which is not in. So to allow loops the definitions must be expanded. For directed simple graphs, the definition of E should be modified to . For directed multigraph, the definition of should be modified to Precisely a clear simple graph requiring loops and a multigram requiring loops (or quavers) can be related to these types of objects to prevent confusion. The edges of a directed simple graph permitting loops G is a homogeneous relation ~ on the vertices of G that is called the adjacency relation of G. Specifically, for each edge (x, y), its endpoints x and y are said to be adjacent to one another, which is denoted denoted A(G), of graph G is an n by n matrix whose (i,j)-th entry is determined as follows: In addition to the graph structure and relationships, adjacent matrices provide an efficient storage and access method in a computer. Therefore, adjacent matrices are one of the most prevalent types of graph representation.

The distance between vertices vi and vj (d(i, j) of a G graph is defined by the path between the two vertices which is the minimum length. Take the graph in Figure 1 for example. Between vertices v6 and v8, there are two paths of length 4 as shown in Figure 2. The graph's corresponding matrix provides a way of estimating the strength of these directions.

Theorem 1. Let G be a graph with adjacency matrix A and k be a positive integer. Then the matrix power Ak gives the matrix where Aij counts the the number of paths of length k between vertices vi and vj. The (6,8)-entry of A4 (G) is required to count all paths between vertices v6 and v8, and the (7,6)-entry is symmetrical. While these results are a useful way to count the number of paths between vertices in a graph it can be expanded to a corollary that is equally interesting and logical. Corollary 1. Let G be a graph with adjacency matrix A and k be a positive integer. Then the sum Sn defined by is the n x n matrix whose (i,j)-entry counts the number of paths of length k or less between vertices vi and vj . Matrices are a useful computer tool to identify and organize the properties of a graph in this sense.

A complete graph G of orders n, denoted Kn, includes an edge between every pair of vertices. K5 is shown in Figure 3, for example. Two sets, U, V ⊂ E(G)for which each vertex of U lies adjacent with each V vertex, and no two vertices within one and the same set. In this case, there is the complete bipartite G in order n = p+q, indicated Kp / q. K2,3 is shown in Figure 4.

The value of a graph G is the value of a matrix corresponding to it. Some fascinating trends for complete graphs – both intermediate and intermediate. Theorem 2. For any positive integer n, the eigenvalues of Kn are n − 1 with multiplicity 1, and −1 with multiplicity n - 1. For any positive integer p, q, the eigenvalues of Kp,q are √pq, − √pq, and 0 with multiplicity p + q − 2. Although this result is self-interesting, this theorem may be used to interweave a simple result in Modern algebra from the graph theory. A graph theory of order n−1 results in the elimination of all vertexes from a complete graph of order n in graph theory. Combining this fact with the above result, this means that every n − k + 1 square submatrix, 1 ≤ k ≤ n, of A(Kn) possesses the eigenvalue −1 with multiplicity k and the eigenvalue n−k+1 with multiplicity 1. Notably, this produces a natural bound on the eigenvalues of the sub matrices of A(Kn):

The incidence matrix, referred to in Q(G), is the n by m matrix with I j)-th input for a G graph of order n and size m is determined as follows: While incidence matrices are not as computer-friendly as adjacent matrices, the Modern algebra retains some interesting characteristics.

First, a note: Q(G) column sums are all zero, so the Q(G) rows are modern since the vector of all 1 occupies the null space of Q. The incidence matrix Q rank for any graph therefore needs to be lower than n. However, only one column is a modern combination for each graph G. of the others: Nevertheless, this lemma only applies to linked graphs that have a path between certain vertices. A graph disconnected is a graph that has no path between at least one pair of vertices. The intuitive notion of not all vertices being on the same section of the graph is provided, as demonstrated by the example in Figure 5.

A part G is called any connected subparagraph of a graph G. There is only one part for linked graphs. We can generate a more general result for any graph using the previous lemma. Theorem 1. If G is a graph on n vertices and has k connected components then rank Q(G) = n − k. Incidence matrices thus capture another dimension of the diagrams. Thus adjacent matrices capture graph density and quantify relationships between vertices, these are related to properties such as node, and thus the incidence matrices are based on the relationships between the edges and vertices.

Let G be a graph with size m and u, v ∈ V (G) (that is, any two vertices u and v of G). The path matrix for vertices u and v – denoted P(u, v) – is the q by m matrix, where q is the number of different paths between u and v, defined as follows: In other words, a path matrix is defined for a certain pair of vertices in a graph G in which • The rows of P(u, v) correspond to the different paths from vertex u to vertex v (which, for example, could be counted using the m-th power of the adjacency matrix Am(G), • The columns of P(u, v) correspond each to an edge in graph G Theorem 2. Let G be a graph of order n, and at least two vertices u, v ∈ V (G). Arrange the columns of its incidence matrix Q(G) such that they align with the columns of the path matrix P(u,v). Then, where M is the matrix having all ones in two rows u and v, and zeros in the remaining n - 2 rows.

The gradation of a vertex vi, as indicated, is that of the total number of vertices, adjacent to vertex i. This is how many edges from this vertex exist, is the degree of each vertex. This gives us an explanation for the concept of Laplacian matrix, which seems totally random at first glance but has a variety of unimaginable properties. The Laplacian Matrix of a Graph G, denoted L(G), is the n by n matrix defined as follows: A laplacian matrix has then, if two vertices are adjacent, the degrees of each vertex along its diagonal axis, and a −1 elsewhere. The other entries consist of all zeros, otherwise. If we define D0(G) to be a diagonal matrix whose entries are the degrees of each vertex, then the Laplacian Matrix of a graph G can be equivalently defined as Significantly, in terms of incidence matrices Laplacian Matrices can also be expressed. The Laplacian matrix of G can be expressed in terms of the incidence matrix when assigning arbitrary orientations to graph G — that is to say assign a fixed, arbitrary path to edge of the oriented representation: For example, take the basic graph in Figure 6:

The Laplacian Matrix for this graph, including its relationship to the adjacency and incidence matrices, is shown in Equation 10:

A graph G tree spanning across is a tree that is a G sub graph. This means a spanning tree is the tree that is at least at one edge on the same vertex as G, using some E(G) sub-set. As you might imagine, it can quickly be a challenging task to count all the spanning sub trees of Graph G. An efficient solution exists however, and Laplacian Matrices are used. Theorem 1 (Matrix Tree Theorem). Let G be a graph of order n. Then the cofactor of any element of L(G) equals the number of spanning trees of G. This implies all Laplacian matrix cofactors are the same, and the common value is the number of the trees covering graph G! Back to the example above Taking the (2,3)-cofactor of the Laplacian Matrix of the triangle: which corresponds to the 3 spanning trees of the graph, depicted in Figure 7.

The graph theory in mathematics is the study of graphs that are mathematical structures that model relationships between objects in a parallel way. A map consists of vertices connected by edges in this sense. A distinction is made between the undirected graphs, where the edges symmetrically link the two

generally considered, see Graph (discrete mathematics). Diagram is one of the major research objects in discrete mathematics. Graph theory, matrix representations related and the characteristics of matrix found in modern algebra. It discussed not only the adjacence matrices of the graphs, but also the more fascinating examples found in incidence matrices. Work explores the utility of these matrix representations for various graph groups, including decoupled graphs, complete graphs and trees.

[1] Graph Matrices. http://compalg.inf.elte.hu/∼tony/Oktatas/TDK/FINAL/Chap%2010. PDF, 2010. [Online; accessed 16-03-2017]. [2] R.B. Bapat (2010). Graphs and Matrices. Hindustan Book Agency, New Delhi, India. [3] Gary Chartrand and Ping Zhang (2012). A First Course in Graph Theory. Dover Publications, Boston. [4] Douglas E. Ensley and J. Winston Crawley (2006). Discrete Mathematics. John Wiley and Sons, Inc., Hoboken, New Jersey. [5] Laszlo Lovasz. Eigenvalues of Graphs. http://www.cs.elte.hu/∼lovasz/eigenvals-x.pdf, 2007. [Online; accessed 17-03-2017]. [6] Damir Vukiccevic and Ivan Gutman (2004). Laplacian Matrix and Distance Matrices in Trees. http://elib.mi.sanu.ac.rs/files/journals/kjm/26/d003download.pdf, 2004. [Online; accessed 17-03-2017]. [7] Mashaghi, A.; et. al. (2004). "Investigation of a protein complex network". European Physical Journal B. 41 (1): pp. 113–121. [8] Vecchio, F. (2017). "Small World" architecture in brain connectivity and hippocampal volume in Alzheimer's disease: a study via graph theory from EEG data". Brain Imaging and Behavior. 11 (2): pp. 473–485. [9] Vecchio, F. (2013). "Brain network connectivity assessed using graph theory in front temporal dementia". Neurology. 81 (2): pp. 134–143. [10] Kumar, Ankush; Kulkarni, G. U. (2016). "Evaluating conducting network based transparent electrodes from geometrical [11] Kepner, Jeremy; Gilbert, John (2011). Graph Algorithms in the Language of Modern Algebra. SIAM. pp. 1171458.

Assistant Professor, Mathematics, Dayanand Science College, Latur vijaysinhgaikwad0@gmail.com