The detection of error and its correction is an important area of mathematics that is vastly constructed in all communication systems. Furthermore, combinatorial design theory has several applications like detecting or correcting errors in communication systems. Network (graph) designs (GDs) are introduced as a generalization of the symmetric balanced incomplete block designs (BIBDs) that are utilized directly in the above mentioned application. The networks (graphs) have been represented by vectors whose entries are the labels of the vertices related to the lengths of edges linked to it. Here, a general method is proposed and applied to construct new networks designs. This method of networks representation has simplified the method of constructing the network designs. In this paper, a novel representation of networks is introduced and used as a technique of constructing the group generated network designs of the complete bipartite networks and certain circulants. A technique of constructing the group generated network designs of the circulants is given with group generated graph designs (GDs) of certain circulants. In addition, the GDs are transformed into an incidence matrices, the rows and the columns of these matrices can be both viewed as a binary nonlinear code. A novel coding error detection and correction application is proposed and examined.
Graph (Network) designs are introduced as a generalization of symmetric balanced incomplete block designs (BIBDs) (see, e.g., [
As defined in [
any edge of
In [
In this paper, a generalization of symmetric BIBDs is investigated and we introduce a new graph representation that will help in constructing new graph designs (GDs).
If
Here, all graphs are assumed to be finite, simple and with non-empty edge set. We use the usual notations:
In our current study, we concentrate on the case when
From now on, all addition and subtraction shall be done modulo
The vertices of
All designs can be represented by a corresponding incidence matrix [
The arrangement of our paper is as follows: In Section 2, a new representation of graphs is introduced. In Section 3, a technique of constructing the group generated graph designs of
In this section, we introduce a new representation of graphs following the method that has been introduced in [
Let
For any subgraph
be the multiset containing the length of every edge in
Let
Let
Let
For
Since all elements of
The elements of the generator
(ii) Let
Then
(iii) For any
So there exist two edges
Then
Therefore,
Case 2. For
For all
Let the set
For all
Then
The rows or columns of the incedence matrix of the GDs can be used as binary codes because all of its entries are 0 or 1. Let us define the GD’s Incedence matrix
For the
As the incidence matrix
Every row has
Every column has
Two distinct columns both have 1s in at most 1 rows.
For illustration, the following example is produced.
The blocks of (
When a GD is transformed into an incidence matrix, the rows and the columns can be both viewed as a binary nonlinear code. The binary codes formed from the row denoted as
The minimum Hamming distance
Distance in binary codes detects the number of errors a code can detect or correct [
a binary code
a binary code
Then for our example
Efficiency factor
To clear the proposed application, we use the above
Words | Codes |
---|---|
Go | 111000000 |
Stop | 000111000 |
Forward | 000000111 |
Back | 100100100 |
Left | 010010010 |
Right | 001001001 |
If the code 111100001 is received. Since number of ones must be 3, the error is detected. To correct the error, the code with the minimum Hamming distance from the received one can be chosen that is 111000000. Then the message is “go,” and so on.
Here, we use the above representation of graphs to construct
Then all graphs in
Since every cell of the
Then all graphs in
Since every cell of the
The existence of
For all
Then all graphs in
Since every cell of the
Then all graphs in
Since every cell of the
Then all graphs in
Since every cell of the
Then all graphs in
Since every cell of the
Then
Since every cell of the
Then
Since every cell of the
Then
Since every cell of the
Then all graphs in
Since every cell of the
Then
Since every cell of the
Then all graphs in
Since every cell of the
Then
Since every cell of the
Then
Since every cell of the
Then all graphs in
Since every cell of the
The elements of the generator
(ii) Let
Then
(iii) For any
So there exist two edges
Then
Therefore,
For all
Then all graphs in
Since every cell of the
Then all graphs in
Since every cell of the
Since
Since every cell of the
|
|
|
|
|
|
||
---|---|---|---|---|---|---|---|
2 | 3 | ||||||
2 | 3 | ||||||
3 | 3 | ||||||
3 | 3 | ||||||
3 | 3 | ||||||
3 | 3 | ||||||
3 | 3 | ||||||
3 | 3 | ||||||
3 | 3 | ||||||
3 | 3 | ||||||
3 | 3 | ||||||
4 | 3 |
In this paper, we have studied the group generated graph designs. A new representation of graphs has been proposed that help in constructing new graph designs
The authors are thankful of the Taif University. Taif University researchers supporting project number (TURSP-2020/031), Taif University, Taif, Saudi Arabia.