Partial Edge Incidence Matrix of Semigraph over GF(22)

Partial Edge Incidence Matrix of Semigraph over GF(22)

Prabhakar R. Hampiholi,

Department of Master of Computer Applications, Gogte Institute of Technology,

Belgaum, India.

Jotiba P. Kitturkar,

Department of Mathematics, Maratha Mandal Engineering College,

Belgaum, India.

AbstractThe notion of a Semigraph is a new concept introduced by E. Sampathkumar, generalizing the concept of a graph. The edges of semigraph contain atleast two vertices and are classified as full edge, subedge and partial edge. In this paper partial edge incidence matrix of semigraph over GF(22) is defined. Also the ranks of two types of semigraphs are obtained.

KeywordsPartial edge incidence matrix; Rank of semigraph.

1. INTRODUCTION

   A matrix is often an eloquent and efficient way of

   vertices of E , represented by small hollow circles. A vertex v in G which appears as end vertex of one edge and middle vertex of the other edge is known as the middlecumend vertex or ((m,e)) vertex, represented by a small tangent to the hollow circle of middle vertex.

   Example 2.2:

   Let G = ( V, X ) be a semigraph (Figure 1) , where

   V = {1, 2, 3, 4, 5, 6, 7, 8 } and X = { (1, 2), ( 2, 3, 4, 5 ), ( 5, 6

   ), ( 2, 7, 6 ), ( 1, 7 ), ( 5, 7 ) } In G, 1, 2, 5, 6 are end vertices, 3 and 4 are middle vertices , 7 is middlecumend vertex and 8 is isolated vertex.

   1

   representing a graph for analysis. There is a relationship 8

   between many graph-theoretical properties and matrix 6

   properties, which makes the problem easier to visualize and

   solve. The authors [2], [4] have studied properties of 7

   semigraph matrices. The author [2] defines the incidence

   matrix and consecutive adjacent matrix of semigraph, but these matrices alone cannot represent semigraph uniquely. As specialty of semigraphs lie in the varieties of definitions and

   concepts, in this paper partial edge incidence matrix of 2

   semigraph over GF(22) is defined, which represent semigraph 5

   uniquely. The results of incidence matrix of graph G [3] are generalized in this paper.

2. PRELIMINARIES

   Definition 2.1 [2]: Semigraph

   A semigraph G is an ordered pair (V, X) where V is a non- empty set, whose elements are called vertices of G and a set X is a set of ntuples, called edges of G, of distinct vertices, for various n 2, with the following conditions :

   SG1: Any two edges have at most one vertex in common. SG2: Two edges 1, 2, . . , and 1, 2, . .. ,

   are equal if and only if

   1. m = n and

   2. either ui = vi or ui = vn-i+1 for i = 1, 2, 3, . . ., n.

   Thus the edge 1, 2, . . , is the same as the edge , 1, . . , 1

   Let G = (V, X) be semigraph and = 1, 2, . . . ,

   1, is an edge of G. Then the vertices v1 and vn are called the end vertices of E, represented by thick dots, the vertices v2 , . . . , vn-1 are called the middle vertices or m

   3 4

   Fig.1 Semigraph G

   In a semigraph, two edges are adjacent if they have a vertex in common. Any two vertices in semigraph are adjacent if they belong to the same edge. In addition if they are consecutive in order then are called as consecutive adjacent vertices.

   Definition 2.3 [2]: Subedge

   A subedge of an edge = 1, 2, . . . is a ktuple

   = ( 1 , 2 , . . . ) where 1 i1 < i2 < · · < ik n or

   1 ik < ik1 < · · < i1 n.

   Definition 2.4 [2]: Partial Edge

   A partial edge of = 1, 2, . . . is a ( j i +1 )tuple (vi , vj) = (vi , vi+1, . . . , vj ), where 1 i n.

   Definition 2.5 [2]: fsedge and fpedge

   fsedge is an edge which is either a full edge or a subedge and fpedge is an edge which is either a full edge or a partial edge.

   Definition 2.6 [5]: Consecutive subedges and consecutive

   partial edges

   Let E = (1 , 2 , . . . . ) be an edge of a semigraph G.

   Two subedges Sj = ( 1 , 2 , . . . . ) where

   vertex vi

   = 2, if mm partial edge is incident on middle vertex v

   1 j1 < j2 < . . . < jn and Sk = ( 1 , 2 , . . . . )

   where 1 < k1 < . . . < km n of E are said to be consecutive subedges if = 1 .

   Two partial edges Pj = ( 1 , 1+1 , . . . . ) and Pk = ( 1 , 1+1 , . . . . ) of E are said to be consecutive partial edges if = 1 .

   An edge E = ( 1 , 2 , . . . . ) has n – 1 partial edges of cardinality two namely P1 = ( 1 , 2 ) ; P2 = ( 2 , 3 ) . . .

   ; Pn-1 = ( 1 , ) such that Pi and Pi+1 are consecutive partial edges for i = 1, 2, . . . , n 2 .

   i

   = 0, otherwise

   The above definition is illustrated in example 3.2

   Example 3.2:

   1

   P1

   P8

   The partial edge P1

   = ( 1

   , 2

   2 P9

   ) is e partial edge if both

   1 and 2 are end vertices and forms an edge. It is mm

   partial edge if both 1 and 2 are middle vertices and me P2

   partial edge if one vertex is middle and other is end.

   Definition 2.7 [2]: Dendroid 3

   4 5 6 7 8

   A dendroid is a connected semigraph without strong cycles. (all edges of strong cycle are fp edges).

   P3 P4

   P5 P6 P7

   Definition 2.8 [6] [7] [8]: Galois Field of prime power GF(

   22)

   Galois Field of prime power GF(22) is the field of

   Fig. 2 Semigraph G

   For the semigraph G (Figure 2), the partial edge incidence matrix B(G) is

   polynomials of degree less than 2 over GF(2)

   modulo (2 + +1) contains four elements { 0, 1, , 2= +1

   } where is a root of the polynomial x2 + x + 1 ( with coefficients in GF(2) ). The addition and multiplication operation on GF(22) are as shown in the Table 1.

   1 0

   0 1

   B(G )= 0 0

   0 0

   0 0

   0 0

   0 0

   0 0

   1 0

   2

   0 2

   0 0

   0 0

   0 0 0 1 1

   0 0 0 0 0

   0 0 0 0 0

   0 0 0 0 0

   2 0 0 0 1

   2 2 0 0 0

   0 2 0 0

   +	0	1		2
   0	0	1		2
   1	1	0	2
   		2	0	1
   2	2		1	0

   ×	0	1		2
   0	0	0	0	0
   1	0	1		2
   	0		2	1
   2	0	2	1

   0 0 0 0

   0 0 1 1 0

   TABLE 1

3. MAIN RESULTS

Now we define the partial edge incidence matrix representation of semigraph.

Definition 3.1: Partial Edge Incidence Matrix of a Semigraph

The partial edge incidence matrix B of a semigraph G is a matrix of order n×m, where n is number of vertices and m is number of consecutive partial edges of cardinality 2 of

Observations 3.3:

In case of partial edge incience matrix,

1. The matrix is of order n × m.

2. Each column corresponds to a consecutive partial edge of cardinality 2 and therefore each column has two non-zero entries as 1 and 1 or 2 and 2 or 1 and .

3. The row sums for epartial edge, mmpartial edge and mepartial edge respective are 0, 0 and 2 with respect to addition defined on GF(22) .

4. deg(vi) = Number of edges having vi as an end vertex

   = Number of 1s in Ri , the ith row .

5. deg (v ) = Number of edges containing v

   semigraph G, is defined as

   bij = 1, if e partial edge or me partial edge is incident on end vertex vi

   = , if me partial edge is incident on middle

   e i i

   = { No. of 1s + ½(Number of s and 2s) } in Ri

6. degca(vi) = Number of vertices which are consecutively adjacent to vi = Number of 1s , s and 2s in Ri

7. The row corresponding to end vertex contain all non zero entries as 1.

8. The row corresponding to middle vertex contains entries or 2 or both.

9. The row corresponding to middlecumend ((m, e)) vertex contains atleast one entry 1 and even number of other non-zero entries.

10. Semigraph can be redrawn using observations 1 to 9.

11) A row with all 0s, therefore, represents an isolated vertex.

12) If a semigraph G is disconnected and consists of two components G1 and G2, then the partial edge incidence matrix B(G) of semigraph G can be written in a block- diagonal form as

Theorem 3.5:

If G is a dendroid with n vertices then the rank of partial edge incidence matrix B(G) is n 1.

Proof: Let B(G) be represented as in Theorem 3.4

Now to prove, the rank of B(G) n 1 , we show that row vectors B1, B2, . . . , Bn of B(G) are linearly dependent.

For this, consider linear combination, b1B1 + b2B2 + b3B3

+ . . . . + bnBn for 0 bi GF(22), for all i = 1, 2, 3, . . n.

Now the bi s are selected in the following ways.

Let Er be any edge in dendroid G. The scalars bi s for Bi s, corresponding to end vertices and middle vertex (vertices) of Er are chosen in one of the 3 ways as shown in the Table 2.

B(G) =

(1)

. 0

. 0

. .

. (2)

The following theorems characterize the partial edge incidence matrix of a semigraph.

Theorem 3.4:

If G is a semigraph with n vertices and not containing middlecumend vertices then the rank of partial edge incidence matrix B(G) is n 1.

Proof: Let B(G) be the incidence matrix of a semigraph G, not containing the middlecumend vertex. Then each row of the incidence matrix B(G) may be regarded as a vector over GF(22). Let the vector in the first row be called B1, in the second row B2, and so on. Thus

1

2

B(G) = .

.

TABLE 2

If Er is the only edge in G then by using these selected bi s for Bi s and Table 1, we see that

b1B1 + b2B2 + b3B3 + . . . . + bnBn = 0 .

Therefore, Bi s are linearly dependent. Hence, the rank of B(G) n 1.

If Er is not the only edge of G, suppose Es is another edge adjacent to Er , then the selection of scalars bi s for rows Bi s corresponding to the vertices of Es depend on common vertex of Er , Es and previously selected bi s for rows Bi s corresponding to the vertices of Er.

In this case, each column of B consists of exactly two

For the common vertex of Er and Es, one of the following cases occurs.

1. If the common vertex is middle vertex of both the edges

   non-zero entries 1 and or and 2 or 2 and 2. Clearly the linear combination ×(sum of the rows B s corresponding to

   Er and Es then pattern of scalar multipliers bi s for Bis

   i

   end vertices) + (sum of the rows Bis corresponding to middle vertices) or {(sum of the rows Bis corresponding to end vertices) + 2×(sum of the rows Bis corresponding to middle vertices)} is zero with respect to GF(22).

   Thus the vectors B , B , . . . ,B are not linearly

   corresponding to vertices of Es is same as selection for bi s

   for Bis corresponding to vertices of Er .

2. If the common vertex is end vertex of both the edges Er and Es then pattern of scalar multipliers bi s for Bis corresponding to vertices of Es is same as selection for bi s

   independent.

   1 2 n

   for Bis corresponding to vertices of Er.

   Therefore, the rank of B is less than n; that is rank B(G) n 1

   Now consider the sum of any l of these n vectors ( l n 1 ). If the semigraph is connected, B(G) cannot be partitioned, such that B(G1) is with l rows and B(G2) with n l rows . In other words, no submatrix of B(G) can be found , for l n 1, such that linear combination of those l rows is equal to zero. Therefore rank B(G) n 1.

   Hence the rank of B(G) = n 1.

   If bi of Bi , corresponding to middle vertex of Er is	Then we select bi of Bi , corresponding to end vertices of Es as	and bi of Bi , corresponding to middle vertex (vertices) of Es as 2
   1	1
   		1
   2	2

   TABLE 3

3. If the common vertex is middle vertex of Er and end vertex of Es and if Bi corresponding to middle vertex of Er is multiplied by bi then the pattern of bi s for Bi s corresponding to vertices of Es is as shown in Table 3.

4. If the common vertex is end vertex of Er and middle vertex of Es and if Bi corresponding to end vertex of Er is multiplied by bi then the pattern of bi s for Bi s corresponding to vertices of Es is as shown in Table 4.

Therefore Bi s are linearly dependent.

Hence rank of B(G) n 1 in all possible cases.

As in Theorem 3.4, we can show that rank B(G) n 1 Therefore, rank B(G) = n 1.

Remark 3.6:

As every graph is a semigraph without middle vertices, by the Theorem 3.4 its rank is n 1, which is also proved by theorem 7-2 [3] page 140. Therefore Theorem 3.4 generalizes the graph theory result.

TABLE 4

If Er and Es are the only two edges in dendroid G then for these selected bi s for Bis and using Table 1, we see that

b1B1 + b2B2 + b3B3 + . . . . + bnBn = 0 .

Hence the rank of B(G) n 1.

If Er and Es are not the only edges of G, suppose Et be one more edge then the above process can be repeated.

Suppose without loss of generality, if Et is adjacent to Er . Then selection of bi s for Bi s of Et depend on previously selected bis of Bis for Er. Continuing this process for all edges we see that

b1B1 + b2B2 + b3B3 + . . . . + bnBn = 0 , for any number of edges.

REFERENCES

1. F. Harary, Graph Theory, Addison-Wesley Publishing Company, 1969

2. E. Sampathkumar, Semigraphs and their application, Technical Report [DST/MS/022/94], Department of Science & Technology, Govt. of India, August 1999.

3. D. Narsingh, Graph Theory with Applications to Engineering and Computer Science, New Delhi: Prentice Hall of India Private Limited, 2000.

4. C. M. Deshpande and Y. S. Gaidhani, About adjacency matrix of semigraphs, International Journal of Applied Physics and Mathematics, Vol. 2, No. 4, pp. 250-252, July 2012.

5. Bhagyashri Athawale, "On some problems of graph theory in semigraphs", Ph.D. Thesis, University of Pune.

6. William Stallings, Cryptography and Network Security Principle and Practice, Pearson, 5th Edition.

7. Shu Lin, Daniel J. Costello, Error Control Coding , Pearson, 2nd Edition, 2013.

8. Nathan Jacobson, Lectures in Abstract Algebra Volume III Theory of Fields And Galois Theory, D.Van Nostrand Company, INC. New York, 1996.