J.
Indones.
Math.
Soc.
Vol.
No.
, pp.
1Ae15.
REGULARITY OF CUBIC GRAPH WITH APPLICATION
Kishore Kumar.
K1 .
Hossein Rashmanlou2 .
Talebi3 .
Mofidnakhaei4 Department of Mathematics.
Al Musanna College of Technology.
Sultanate of Oman kishorePK@act.
Department of Computer Science.
University College of Adib.
Sari.
Iran 1987@gmail.
Department of Mathematics.
University of Mazandaran.
Babolsar.
Iran talebi@umz.
Department of Physics.
Sari Branch.
Islamic Azad University.
Sari.
Iran Farshid.
Mofidnakhaei@gmail.
Abstract.
A cubic graph is a generalized structure of a fuzzy graph that gives more precision, flexibility and compatibility to a system when compared with systems that are designed using fuzzy graphs.
In this paper, some properties of an edge regular cubic graph are given.
Particularly, strongly regular, edge regular and bi-regular cubic graphs are defined and the necessary and sufficient condition for a cubic graph to be strongly regular is studied.
Likewise, we have introduced a partially edge regular cubic graph and fully edge regular cubic graph with suitable Finally, we gave an application of cubic digraph in travel time.
Key words and Phrases: Cubic graph, strongly regular cubic graph, bi-regular cubic graph Abstrak.
Graf kubik merupakan suatu struktur perumuman dari graf fuzzy yang memberikan banyak presisi, fleksibilitas, dan kompatibilitas terhadap suatu sistem yang dirancang menggunakan graf fuzzy.
Dalam paper ini, dipelajari beberapa sifat dari suatu graf kubik yang teratur sisi.
Didefinisikan pula graf kubik teratur kuat yang teratur sisi dan bi-regular serta dipelajari syarat perlu dan syarat cukup bagi suatu graf kubik agar menjadi graf yang teratur kuat.
Kemudian, diperkenalkan graf kubik yang teratur sisi secara parsial dan graf kubik teratur sisi secara penuh dengan beberapa ilustrasi diberikan.
Terakhir, diberikan aplikasi dari graf kubik pada travel time.
Kata kunci: Graf kubik.
Graf kubik teratur kuat.
Graf kubik bi-regular.
2000 Mathematics Subject Classification: 05C72, 05C99.
Received: 25-08-2017, revised : 20-05-2018, accepted: 31-05-2018.
Kumar.
Rashmanlou.
Talebi, and F.
Mofidnakhaei INTRODUCTION Zadeh introduced the concept of fuzzy set in his seminal paper .
A fuzzy set of a universe X is a function from X into the unit closed interval .
, .
of real number.
In .
Zadeh made an extension of the concept of a fuzzy set by an interval-valued fuzzy set, i.
, a fuzzy set with an interval-valued membership function.
The first definition of fuzzy graphs was proposed by Kaufmann .
Interval-valued fuzzy sets have been actively used in real-life applications.
For example.
Sambuc .
in medical diagnosis in thyroidian pathology.
Kohout .
also in medicine.
Turksen in preferences modeling .
These works and others showed the importance of these sets.
Jun et al.
introduced cubic sets.
The fuzzy graph theory as a generalization of EulerAos graph theory was first introduced by Rosenfeld .
Later.
Bhattacharya .
gave some remarks on fuzzy graphs and some operations on fuzzy graphs were introduced by Mordeson and Peng .
The complement of a fuzzy graph was defined by Mordeson .
and further studied by Sunitha and Vijayakumar .
Hongmei and Lianhua gave the definition of interval-valued fuzzy graphs .
Akram and Dudek defined some operations on intervalvalued fuzzy graphs .
Rashmanlou et al.
, 11, .
introduced some properties of highly irregular interval-valued fuzzy graphs, and new concepts of bipolar fuzzy graphs.
Karunambigai et al.
introduced edge regular intuitionistic fuzzy graph.
Samanta and Pal .
, 16, 17, 18, 19, .
defined fuzzy tolerance graph, fuzzy threshold graph, fuzzy kcompetition graph and p-competition fuzzy graph and new concepts of fuzzy planar graph.
The major role of cubic graph theory in computer applications is the development of graph These algorithms are used to solve problems that are modeled in the form of graphs and the corresponding computer science application problems.
One of the most widely studied classes of cubic graphs is regular cubic graphs.
Theoretical concepts of cubic graphs are highly utilized by computer science applications.
Especially in research areas of computer science such as data mining, image segmentation, clustering, image capturing and networking.
The cubic graphs are more flexible and compatible than fuzzy graphs due to the fact that they have many applications in networks.
They show up in many Fore example, r-regular cubic graphs with connectivity and edge-connectivity equal to r play a key role in designing reliable communication networks.
Hence, in this paper some properties of an edge regular cubic graph are given.
Particularly, strongly regular, edge regular and biregular cubic graphs are defined and the necessary and sufficient condition for a cubic graph to be strongly regular is studied.
Also, we have introduced a partially edge regular cubic graph and fully edge regular cubic graph with suitable illustrations.
After introductory Section 1, some basic definitions are given in Section 2.
In Section 3, the concepts of regularity of cubic graphs are defined.
In Section 4, an application is given in travel time.
At last conclusion is given in Section 5.
PRELIMINARIES
A graph is an ordered pair G = (V.
E), where V is the set of vertices of G and E is the set of edges of G.
A subgraph of a graph G = (V.
E) is a graph H = (W.
F), where W OI V and F OI E.
A fuzzy graph G = (E.
AA) is a pair of functions E : V Ie .
, .
and AA : V y V Ie .
, .
with AA.
, .
O E.
O E.
, for all u, v OO V, where V is a finite non-empty set and O denote minimum.
We introduce below necessary notions and present Regularity Of Cubic Graph With Application a few auxiliary results that will be used throughout the paper.
A map : X Ie .
, .
is called a fuzzy subset of X.
For any two fuzzy subsets and AA of X.
OI AA means that, for all x OO X, .
O AA.
The symbol O AA and O AA will mean the following fuzzy subsets of X.
( O AA).
= .
O AA.
and ( O AA).
= .
O AA.
, for all x OO X.
Let X be a non-empty set.
A function A : X Ie [I] is called an interval-valued fuzzy set .
hortly, an IVF se.
in X.
Let [I]X stands for the set of all IVF sets in X.
For every A OO [I]X and x OO X,A.
= [AOe .
A .
] is called the degree of membership of an element x to A, where AOe : X Ie I and A : X Ie I are fuzzy sets in X which are called a lower fuzzy set and an upper fuzzy set in X, respectively.
For simplicity, we denote A = [AOe .
A ].
For every A.
B OO [I]X , we define A OI B if and only if A.
O B.
, for all x OO X.
Definition 2.
Let A = [AOe .
A ], and B = [BOe .
B ] be two interval-valued fuzzy set in X.
Then we define rmin{A.
} = .
in{AOe .
BOe .
}, min{A .
B .
}], rmax{A.
} = .
ax{AOe .
BOe .
}, max{A .
B .
}].
Definition 2.
Let X be a non-empty set.
By a cubic set in X, we mean a structure A = {< x.
, .
: x OO X >} in which A is an interval-valued fuzzy sets in X and is a fuzzy set in X.
A cubic set A = {< x.
, .
: x OO X >} is simply denoted by A =< A, >.
The collection of all cubic sets in X is denoted by CP(X).
Definition 2.
A cubic graph is a triple G = (GO .
Q) where GO = (V.
E) is a graph.
P = .
AAP .
P ) is a cubic set on V and Q = .
AAQ .
AAf Q ) is a cubic set on V y V such that fP .
} and f AAf AAP .
AA Q .
O rmin.
Q .
Ou rmax{P .
, fP .
} The underlying crisp graph of a cubic graph G = (A.
B), is the graph G = (V.
E), fP >0 and P >.
and E = .
, .
: AAf where V = .
: AA Q (.
, .
)>0.
AA Q (.
, .
)>0 .
V is called the vertex set and E is called the edge set.
A cubic graph maybe also denoted as G = (V.
E).
Definition 2.
A cubic graph G = (GO .
Q) is called complete if AAf Q .
= rmin{AAP .
AAP .
} and f .
, fP .
} for all x, y OO V.
Definition 2.
A cubic graph G = (GO .
Q) is called strong if AAf Q .
= rmin{AAP .
AAP .
} and f .
, .
} OO Definition 2.
The complement of a cubic graph G = (A.
B) is a cubic graph G = (GO .
Q), where P = .
AAP .
P ) and Q = .
AAQ .
Q ) is defined by: AAf Q .
= rmin{AAP .
AAP .
}Oe AAf Q .
and Q .
= Q .
Oe rmax{P .
P .
} Definition 2.
Let G = (V.
E) be a cubic graph.
The neighborhood degree of a vertex v is defined as DN .
= dNAAfP .
, dNQ .
, where P fOe .
P AA .
and dN .
= P Q .
dN .
= AAP fOe ) wOON(AA wOON(AA P ) Q wOON(Q ) .
The degree of a vertex vi is defined by dG .
i ) = dAAfP .
i ), dQ .
i ) = .
1 , k2 ), where Kumar.
Rashmanlou.
Talebi, and F.
Mofidnakhaei k1 = dAAfP .
i ) = Oe AAf Q .
i v j ), vi ,v j and k2 = dQ .
i ) = AAf Q .
i v j ) vi ,v j Q .
i v j ).
vi ,v j Definition 2.
A cubic graph G = (V.
E) is said to be .
1 , k2 )Oeregular if dG .
i ) = .
1 , k2 ), for all vi OO V and also G is said to be a regular cubic graph of degree .
1 , k2 ).
bipartite if the vertex set V can be partitioned into two non-empty sets V1 and V2 such .
AAf Q .
i v j ) = 0 and Q .
i v j ) = 0, if .
i , v j ) OO V1 or .
i , v j ) OO V2 .
AAf Q .
i v j ) = 0.
Q .
i v j ) > 0, if vi OO V1 or v j OO V2 .
AAf Q .
i v j ) > 0.
Q .
i v j ) = 0, if vi OO V1 or v j OO V2 , for some i and j.
Definition 2.
Let GO = (V.
E) be a crisp graph and let e = vi v j be an edge in GO .
Then, the degree of an edge e = vi v j OO E is defined as dGO .
i v j ) = dGO .
i ) dGO .
j ) Oe 2.
Definition 2.
The order of G is defined to be O(G) = OAAfP .
OP , where OAAfP = uOOV AAP .
and OP = uOOV P .
The size of G is defined to be S (G) = (S AAfQ (G).
S Q (G)), where S AAfQ (G) = u,v AA] Q .
and S Q (G) = u,v Q .
Isomorphic properties of neighborly irregular and highly irregular cubic graphs In this section, we define weak isomorphism, co-weak isomorphism and isomorphism of neighborly irregular cubic graphs and prove that.
Definition 3.
Let G = (V.
E) be a cubic graph.
The degree of an edge ei j OO E is defined as vk v j OOE AA dAAfQ .
i j ) = dAAfP .
i ) dAAfP .
j ) Oe 2f AAQ .
i v j ) or dAAfQ .
i j ) = AAf Q .
i vk ) Q .
k v j ).
vi vk OOE X k, j dQ .
i j ) = dP .
i ) dP .
j ) Oe 2Q .
i v j ) or dQ .
i j ) = Q .
i vk ) vk v j OOE Q .
k v j ).
vi vk OOE k, j .
The minimum edge degree of G is E (G) = (AAfQ (G).
Q (G)), where AAfQ (G) = O.
AAfQ .
i j ) | ei j OO E} and Q (G) = O.
Q .
i j ) | ei j OO E}.
The maximum edge degree of G is OIE (G) = (OIAAfQ (G).
OIQ (G)), where OIAAfP (G) = O.
AAfQ .
i j ) | ei j OO E} and OIQ (G) = O.
Q .
i j ) | ei j OO E}.
The total edge degree of Xan edge ei j OO E is defined as X AAf AAQ .
i j ), tdQ .
i j ) = Q .
i vk ) Q .
k v j ) AAf tdAAfQ .
i j ) = Q i k Q .
k v j ) f vi vk OOE k, j vk v j OOE vi vk OOE k, j vk v j OOE Q .
i j ).
The edge degree of G is defined by dG .
i j ) = .
AAfQ .
i j ), dQ .
i j )) and the total edge degree of G is defined by tdG .
i j ) = .
dAAfQ .
i j ), tdQ .
i j )).
Example 3.
Consider the cubic graph G = (V.
E) in Figure 3.
1, where V = .
, b, c, .
and E = .
b, ad, bc, bd, c.
Then Regularity Of Cubic Graph With Application Figure 1.
Cubic graph dAAfQ .
= .
7, 1.
, dQ .
= 1.
1,dG .
= .
7, 1.
, 1.
1, tdAAfQ .
= .
1 = 0.
8, 1.
25 = 1.
and tdQ .
= 1.
4 = 2.
Hence, tdG .
= .
8, 1.
, 2.
i j = .
i , u j )).
Definition 3.
Let G = (V.
E) be a cubic graph.
If each edge in G has the same degree .
1 , l2 ), then G is said to be an edge regular cubic .
If each edge in G has the same total degree .
1 , t2 ), then G is said to be a totally edge regular cubic graph.
Example 3.
Consider the cubic graph G = (V.
E) as in Figure 2, where V = .
1 , u2 , u3 , u4 } and E = .
1 u2 , u1 u3 , u3 u4 , u2 u4 }.
Then dG .
12 ) = dG .
24 ) = dG .
34 ) = dG .
13 ) = .
1, 0.
, 1.
Theorem 3.
Let G = (V.
E) be a cubic graph on a cycle GO .
Then dG .
i ) = dG .
i v j ) vi OOV vi v j OOE Proof.
Let G = (V.
E) be a cubic graph and GO be a cycle v1 v2 v3 A A A vn v1 .
Then Oe fP = {AAOeP .
AA P } and AAf dQ .
i vi 1 ) .
Also AA dG .
i vi 1 ) = dAAfQ .
i vi 1 ).
Q = {AAQ .
AAQ } Now we have .
i vi 1 ) = i=1 dAAf dAAfQ .
1 v2 ) dAAfQ .
2 v3 ) A A A dAAfQ .
n v1 ), where vn 1 = v1 = dAAfP .
1 ) dAAfP .
2 )Oe2f AAQ .
1 v2 ) dAAfP .
2 ) dt .
3 ) = 2f AAP .
2 v3 ) A A A dAAfP .
n ) dAAfP .
1 ) Oe 2f AAQ .
n v1 ) = 2dAAfP .
1 ) 2dAAfP .
2 ) A A A 2dAAfP .
n ) Kumar.
Rashmanlou.
Talebi, and F.
Mofidnakhaei Figure 2.
1,0.
,1.
1 - edge regular cubic graph = 2 AAf Q .
1 v2 ) AA Q .
2 v3 ) A A A AA Q .
n v1 ) = 2 vi OOV dAAfP .
i ) Oe2 i=1 AAf Q .
i vi 1 ) = vi OOV dAAfP .
i ) 2 ni=1 AAf Q .
i vi 1 ) Oe2 i=1 AAf Q i i 1 fP .
i ).
= vi OOV AA dP .
i ).
Similarly, dQ .
i vi 1 ) = vi OOV Hence, ni=1 dG .
i vi 1 ) = fP .
i ), vi OOV dAA vi OOV dP .
i ) = vi OOV dG .
i ).
Remark 3.
Let G = (V.
E) be a cubic graph on a crisp graph G .
Then, vi v j OOE dG .
i v j ) = AAQ .
i v j ), vi v j OOE dGO .
i v j )f vi v j OOE dGO .
i v j )Q .
i v j ) , where dGO .
i v j ) = dGO .
i ) dGO .
j ) Oe 2, for all vi v j OO E.
Theorem 3.
Let G = (V.
E) be a cubic graph on a kOeregular crisp graph GO .
Then, fP .
i ), .
Oe .
vi OOV dP .
i ) .
vi v j OOE dG .
i v j ) = .
Oe .
vi OOV dAA Proof.
By Remark 3.
6, we have vi v j OOE dG .
i v j ) = ( vi v j OOE dGO .
i v j )f AAQ .
i v j ), vi v j OOE dGO .
i v j )Q .
i v j )) AAQ .
i v j ), vi v j OOE .
GO .
i ) dGO .
j ) Oe .
f O vi v j OOE .
GO .
i ) dGO .
j ) Oe .
Q .
i v j ) .
Since G is a regular crisp graph, dGO .
i ) = k, for all vi OO V and so we have vi v j OOE dG .
i v j ) = .
k Oe .
vi v j OOE AAf Q .
i v j ), .
k Oe .
vi v j OOE Q .
i v j ) , vi v j OOE dG .
i v j ) = 2.
Oe .
vi v j OOE AAf Q .
i v j ), 2.
Oe .
vi v j OOE Q .
i v j ) , .
i ), .
Oe .
vi OOV dQ .
i ) .
vi v j OOE dG .
i v j ) = .
Oe .
vi OOV dAAf Regularity Of Cubic Graph With Application Theorem 3.
Let G = (V.
E) be a cubic graph on a crisp graph GO .
Then, vi vi OOE tdG .
i v j ) = AAQ .
i v j ) vi v j OOE AAf Q .
i v j ), vi v j OOE dGO .
i v j )f vi v j OOE dGO .
i v j )Q .
i v j ) vi v j OOE Q .
i v j ) .
Proof.
By definition of total edge degree of G, we have vi v j OOE tdG .
i v j ) = tdAAfQ .
i v j ), vi v j OOE tdQ .
i v j ) i v j OOE vP .
i v j ) AAf Q .
i v j )), vi v j OOE .
AAf vi v j OOE .
Q .
i v j ) Q .
i v j )) d .
i v j ) P vi v j OOE AAfQ Q .
i v j ), vi v j OOE AA vi v j OOE Q .
i v j ) vi v j OOE Q .
i v j ) .
By Remark 3.
6, we get td .
v ) P vi v j OOE G i j dGO .
i v j )f AAQ .
i v j ) P vi v j OOE d O .
v ) .
v ) vi v j OOE vi v j OOE G i j Q i j vi v j OOE Q .
i v j ) .
Theorem 3.
Let G = (V.
E) be a cubic graph.
Then .
B , fB ) is a constant function if and only if the following are equivalent.
G is a edge regular cubic graph.
G is totally edge regular cubic graph.
Proof.
Assume that .
AAP .
Q ) is a constant function.
Then AAf Q .
i v j ) = c1 and Q .
i v j ) = c2 , for every vi v j OO E, where c1 and c2 are constants.
Let G be an .
1 , l2 )-edge regular cubic graph.
Then, for all vi v j OO E, dG .
i v j ) = .
1 , l2 ) and tdG .
i v j ) = .
AAfP .
i v j ) AAf Q .
i v j ), dQ .
i v j ) Q .
i v j )) = .
1 c1 , l2 c2 ), for all vi v j OO E.
Then G is a totally edge Now, let G be a .
1 , t2 )Oetotally edge regular cubic graph.
Then tdG .
i v j ) = .
1 , t2 ), for all vi v j OO E.
So, we have tdG .
i v j ) = .
AAfQ .
i v j ) f AAP .
i v j ), dQ .
i v j ) Q .
i v j )) = .
1 , t2 ).
Hence, .
AAfQ .
i v j ), dQ .
i v j )) = .
1 Oe AAf Q .
i v j ), t2 Oe Q .
i v j )) = .
1 Oe c1 , t2 Oe c2 ).
Then.
G is a .
1 Oe c1 , t2 Oe c2 ) edge regular cubic graph.
Conversely, assume that .
are equivalent.
We have to prove that .
AAP .
Q ) is a constant function.
Suppose that .
AAP .
Q ) is not a constant function.
Then AAf Q .
i v j ) .
AAf Q .
r v s ) and Q .
i v j ) .
Q .
r v s ) for at least one pair of vi v j , vr v s OO E.
Let G be an .
1 , l2 ) edge regular cubic graph.
Then, dG .
i v j ) = dG .
r v s ) = .
1 , l2 ).
Hence for all vi v j OO E and for all vr v s OO E.
tdG .
i v j ) = .
AAfQ .
i v j ) AAf Q .
i v j ), dQ .
i v j ) Q .
i v j )) = .
1 f AAQ .
i v j ), l2 Q .
i v j )) tdG .
r v s ) = .
AAQ .
r v s ) f AAQ .
r v s ), dQ .
r v s ) Q .
r v s )) = .
1 AAQ .
r v s ), l2 Q .
r v s )) Since.
AAf Q .
i v j ) .
AA Q .
r v s ) and Q .
i v j ) .
Q .
r v s ), we have tdG .
i v j ) , tdG .
r v s ).
Hence.
G is not a totally edge regular that is contradiction to our assumption.
Therefore, .
AAP .
Q ) is a constant function.
Similarly we can show that .
AAP .
Q ) is a constant function, when G is a totally edge regular cubic graph.
Theorem 3.
Let G = (V.
E) be a cubic graph on a kOeregular crisp graph GO .
Then, .
B , fB ) is a constant if and only if G is both regular and edge regular cubic graph.
Kumar.
Rashmanlou.
Talebi, and F.
Mofidnakhaei Figure 3.
Strongly regular cubic graph Proof.
Let G = (V.
E) be a cubic graph on GO and let GO be a kOeregular crisp Assume that AAf Q and Q are constant functions, i.
Q .
i v j ) = c and Q .
i v j ) = t, for all vi v j OO E, where c, t are we have of Pa vertex P dG .
i ) = .
AAfP .
i ), dQ .
i )) = Q .
i v j ), vi v j OOE AA vi v j OOE Q .
i v j ) = vi v j OOE c, vi v j OOE t for all vi OO V.
Hence, dG .
i ) = .
c, k.
Therefore.
G is regular cubic graph.
Now, tdG .
i v j ) = .
dAAfQ .
i v j ), tdQ .
i v j )), where tdt .
i v j ) = f.
v ) f AAf .
v ) AA AAQ .
i v j ) PQ i k P P k j = vi vk OOE c vk v j OOE c c = c.
Oe.
Oe.
c = c.
kOe.
Similarly, tdQ .
i v j ) = t.
kOe.
, k, j for all vi v j OO E.
Hence.
G is also totally edge regular cubic graph.
Conversely, assume that G is both regular and edge regular cubic graph.
We prove that .
AAQ .
Q ) is a constant function.
Since G is regular, dG .
i ) = .
1 , c2 ), for all vi OO V.
Also.
G is totally edge regular.
Hence tdG .
i v j ) = .
1 , t2 ), for all vi v j OO E.
By definition of totally edge degree we have tdG .
i v j ) = .
dAAfQ .
i v j ), tdQ .
i v j )), where tdG .
i v j ) = dAAfP .
i ) dAAfP .
j ) Oe AAf Q .
i v j ), for all vi v j OO E, t1 = c1 c2 Oe AA Q .
i v j ).
So.
AA Q .
i v j ) = 2c1 Oe t1 .
Similarly we have Q .
i v j ) = 2c2 Oe t2 , for all vi v j OO E.
Hence, .
AAP .
Q ) is a constant Definition 3.
A cubic graph G = (V = .
1 , v2 .
A A A , vn }.
E), is said to be strongly regular, if it satisfies the following axioms:
G is k = .
1 , k2 )Oeregular cubic graph .
The sum of membership values and non-membership values of the common neighborhood vertices of any pair of adjacent vertices and non-adjacent vertices vi , v j of G has the same weight and is denoted by = .
1 , 2 ), = .
1 , 2 ), respectively.
Note 3.
Any strongly cubic graph G is denoted by G = .
, k, , ).
Example 3.
Consider the cubic graph G = (V.
E) in Figure 3, where V = .
, b, .
and E = .
Then, n =bc, 4, c.
k = .
e1 , k2 ) = (.
2, 0.
, 1.
= .
, 2 .
O ) = [.
4, 0.
, 1.
= .
1 , 2 ) = [.
, .
, .
Hence.
G is a strongly regular cubic graph.
Theorem 3.
If G = (V.
E) is a complete cubic graph with .
A , fA ) and .
B , fB ) as constant functions, then G is a strongly regular cubic graph.
Regularity Of Cubic Graph With Application Proof.
Let G = (V.
E) be a complete cubic graph where V = .
1 , v2 .
A A A , vn }.
Since fP .
i ) = r, ( vi ) = s.
AA] P i Q .
i ).
AAP .
i v j ) and Q .
i v j ) are constant functions, hence.
AA fP .
i v j ) = c and Q .
i v j ) = t, for all vi v j OO E where r, s, c, t are for all vi OO V and AA To prove that G is a strongly regular cubic graph, we have to show that G is k = .
1 , k2 )Oeregular cubic graph and the adjacent vertices have the same common neighborhood = .
, 2 ) and non-adjacent vertices have the same common Pneighborhood fP .
i v j ), = .
, 2 ).
Now.
Since G is complete.
dG .
i ) = .
AAfP .
i ), dQ .
i )) = vi v j OOE AA vi v j OOE Q .
i v j ) = (.
Oe .
c, .
Oe .
Hence.
G is an (.
Oe .
c, .
Oe .
Oeregular cubic graph.
Now, since G is complete cubic graph, the sum of membership values and non-membership values of common neighborhood vertices of any pair of adjacent vertices = (.
Oe.
r, .
Oe.
are the same and the sum of membership values and non-membership values of common neighborhood vertices of any pair of non-adjacent vertices = 0 are the Remark 3.
If G is a strongly regular disconnected cubic graph then, = 0.
Definition 3.
A cubic graph G = (V.
E) is said to be a biregular cubic graph if it satisfies the following axioms:
G is k = .
1 , k2 )Oeregular cubic graph.
V = V1 O V2 be the bipartition of V and every vertex in V1 has the same neighborhood degree M = (M1 .
M1 ) and every vertex in V2 has the same neighborhood degree N = (N1 .
N2 ), where M and N are constants.
Example 3.
Consider a cubic graph G = (V.
E) in Figure 4, where V = .
1 (.
25, 0.
, 0.
u2 (.
35, 0.
, 0.
u3 (.
25, 0.
, 0.
, u4 (.
35, 0.
, 0.
u5 (.
35, 0.
, 0.
, u6 (.
25, 0.
, 0.
u7 (.
35, 0.
, 0.
, u8 (.
25, 0.
, 0.
and E = .
1 u2 , u1 u4 , u1 u5 , u2 u6 , u2 u3 , u3 u4 , u3 u7 , u4 u8 , u5 u6 , u5 u8 , u6 u7 , u7 u8 }.
The membership values of the edges .
1 , u2 ), .
3 , u4 ), .
5 , u8 ), .
6 , u7 ) is (.
05, 0.
, 0.
and that of .
1 , u4 ), .
2 , u3 ), .
5 , u6 ), .
7 , u8 ) is (.
15, 0.
, 0.
and that of .
1 , u5 ), .
2 , u6 ), .
4 , u8 ), .
3 , u7 ) is (.
25, 0.
, 0.
Then n = 8, k = .
1 , k2 ) = (.
55, 0.
, 1.
V1 = .
1 , u3 , u6 , u8 }.
V2 = .
2 , u4 , u5 , u7 }.
M = (M1 .
M2 ) = (.
15, 1.
, 1.
and N = (N1 .
N2 ) = (.
85, 0.
, 1.
Theorem 3.
If G = (V.
E) is a strongly regular cubic graph which is strong then.
G is a .
1 , k2 )Oeregular.
Proof.
Let G = (V.
E) be a strongly regular cubic graph.
Then by definition.
G is a .
1 , k2 )Oeregular.
Since G is strong, we have f or all vi v j OO E AAf Q .
i v j ) = fP .
j )) f or all vi v j < E AAP .
i ).
AA f or all vi v j OO E Q .
i v j ) = max(P .
i ).
P .
j )) f or all vi v j < E.
Kumar.
Rashmanlou.
Talebi, and F.
Mofidnakhaei Figure 4.
Biregular cubic graph Now, since G is strong, the degree of a vertex vi in G is dGE .
i ) = .
AAfAP .
i ), dAP .
i )), where AQ .
i v j ) = Pv ,v e dAAfAP .
i ) = vi ,v j AAf AAPE .
i ) O e AAPE .
j ) = k1 .
OAvi OO V Hence, dGE .
i ) = .
1 , k2 ), for all vi OO V.
So.
G is a .
1 , k2 )-regular cubic graph.
Theorem 3.
Let G = (V.
E) be a strong cubic graph.
Then G is a strongly regular if and only if G is a strongly regular.
Proof.
Assume that G = (V.
E) is a strongly regular cubic graph.
Then G is .
1 , k2 )Oeregular and the adjacent vertices and the non-adjacent vertices have the same common neighborhood = .
, 2 ) and = .
, 2 ), respectively.
We have to prove that G is a strongly regular cubic graph.
If G is strongly regular cubic graph which is strong then G is a .
1 , k2 )Oeregular cubic graph by Theorem 3.
Next, let S 1 and S 2 be the sets of all adjacent vertices and non-adjacent vertices of G.
That is.
S 1 = .
i v j | vi v j OO E}, where vi and v j have same common neighborhood = .
, 2 ) and S 2 = .
i v j | vi v j < E}, where vi and v j have same common neighborhood = .
, 2 ).
Then.
S 1 = .
i v j | vi v j OO E}, where vi and v j have same common neighborhood = .
, 2 ) and S 2 = .
i v j | vi v j < E}, where vi and v j have same common neighborhood = .
, 2 ).
Which implies G is a strongly regular.
Similarly we can prove the converse.
Theorem 3.
A strongly regular cubic graph G is a biregular cubic graph if the adjacent vertices have the same common neighborhood = .
, 2 ) , 0 and the non-adjacent vertices have the same common neighborhood = .
, 2 ) , 0.
Proof.
Let G = (V.
E) be a strongly regular cubic graph.
Then we have d.
i ) = .
1 , k2 ), for all vi OO V.
Assume that the adjacent vertices have the same common neighborhood = .
, 2 ) , 0.
Let S be the sets of all non-adjacent vertices.
That is S = .
i v j | vi is not adjacent to v j , i , j, vi , v j OO V}.
Now the vertex partition of G is V1 = .
i | vi OO S } and V2 = .
j | v j OO S }.
Then V1 and V2 have the same neighborhood degree, since G is a strongly regular.
Hence.
G is a bi-regular cubic graph.
Definition 3.
If the underlying graph GO is an edge regular graph, then G is said to be a partially edge regular cubic graph.
Regularity Of Cubic Graph With Application .
If G is both edge regular and partially edge regular cubic graph, then G is said to be a full edge regular cubic graph.
Theorem 3.
Let G be a cubic graph on GO such that .
B , fB ) is a constant function.
G is full regular, then G is full edge regular cubic graph.
Proof.
Let .
AAQ .
Q ) be a constant function.
Then.
AAf Q .
i v j ) = c1 and Q .
i v j ) = c2 , for every vi v j OO E where c1 and c2 are constants.
Suppose that G is full regular cubic graph then dG .
i ) = .
1 , k2 ) = k and dGO .
i ) = r, for all vi OO V, where k and r are constants.
dGO .
i v j ) = dGO .
i ) dGO .
j ) Oe 2 = 2r Oe 2 =constant.
Hence.
GO is an edge regular graph.
Now, since G is regular, dG .
i v j ) = .
AAfQ .
i v j ), dQ .
i v j )), for all vi v j OO E where dAAfQ .
i v j ) = dAAfP .
i ) dAAfP .
j ) Oe 2f AAQ .
i v j ) = k1 k1 Oe 2c1 = 2k1 Oe 2c1 = constant.
Similarly, for all vi v j OO E, dQ .
i v j ) = 2k2 Oe 2c2 = constant.
Hence.
G is an edge regular cubic graph.
Therefore.
G is full edge regular cubic graph.
Theorem 3.
Let G be a tOetotally edge regular cubic graph and t1 Oepartially edge regqt , where q = |E|.
ular cubic graph.
Then S (G) = 1 t1 Proof.
The size of cubic graph G is X
S (G) =
AAf Q .
i v j ) .
Q .
i v j ), vi v j OOE vi v j OOE Since G is tOetotally edge regular cubic graph i.
, tdG .
i v j ) = t and P G is t1 Oepartially edge regular cubic graph i.
dGO .
i v j ) = t1 .
Thus, tdG .
i v j ) = AAQ .
i v j ), vi v j OOE dGO .
i v j )f vi v j OOE dGO .
i v j ) Q .
i v j ) S (G).
qt = t1 S (G) S (G).
Hence.
S (G) = 1 t1
CUBIC DIGRAPH IN TRAVEL TIME
In modern age, planning efficient routes is essential for industry and business, with applications as varied as product distribution, laying new fiber optic lines for broadband internet, and suggesting new friends within social network websites such as Facebook.
When we visit a website like Google Maps and looking for directions from one city to another city in USA, we are usually asking for a shortest path between the two cities.
These computer applications use representations of the road maps as graphs, with estimated travel times as edge weights.
The travel time is a function of traffic density on the road or the length of the road.
The traffic density is a fuzzy, while the length of a road is a crisp In a road network, crossings are represented by vertices, roads by edges and traffic density on the road is usually calculated between adjacent crossings.
These factors can be represented as a cubic set.
Any model of a road network can be represented as a cubic digraph D = (C.
R),where C is a cubic set of crossings.
at which the traffic density is calculated and connectivity conditions as truth-membership degree with intervals fP .
n and falsity membership degree P .
C = .
, .
2, 0.
, 0.
, .
, .
3, 0.
, 0.
, .
, .
5, 0.
, 0.
, .
4, 0.
, 0.
, .
, .
2, 0.
, 0.
, ( f, .
3, 0.
, 0.
, .
, .
4, 0.
, 0.
and R is a cubic set of roads .
between crossings whose truth membership degree Kumar.
Rashmanlou.
Talebi, and F.
Mofidnakhaei fP .
and false membership degree P .
can be calculated as:
fP .
} AAf AAP .
AA Q .
O min.
P .
Ou max{P .
P .
} for all xy OO E.
Figure 5.
Cubic digraph of a road network Figure 6.
Weighted digraph of a road network Regularity Of Cubic Graph With Application The cubic digraph D = (C.
R) of the travel time is given in Figure 5.
The cubic out neighborhood are given in Table 4.
The final weights on edges can be calculated by finding the score function of cubic edges si = .
AAR )i 1 Oe (R )i .
The final weighted digraph given in Figure 6 which can be used for finding the shortest or optimal path between two locations .
by any of the known methods, like FloydAos algorithm.
DjikstraAos and A star algorithm.
Weighted relations are given in Table 4.
Crossings Crossings N .
,(.
1,0.
,0.
,(.
1,0.
,0.
, g,(.
2,0.
,0.
,(.
2,0.
,0.
,(.
3,0.
,0.
,(.
1,0.
,0.
,(.
2,0.
,0.
, e,(.
1,0.
,0.
,(.
1,0.
,0.
, f,(.
1,0.
,0.
N .
,0.
,0.
6 , g,0.
,0.
,0.
,0.
,0.
65, e,0.
,0.
7, f,0.
The following algorithm generates the weighted digraph.
WR, for given cubic digraph and resolves to obtain the optimal path from a source vertex to destination vertex.
CONCLUSION
Fuzzy graph theory has numerous applications in modern science and technology, especially in the fields of operations research, neural networks, and decision making.
Since the cubic models give more precision, flexibility and compatibility to the system as compared to the classical and fuzzy models, in this paper the definition of partial edge regular and fully edge regular cubic graph are given and some properties of edge regular cubic graph are studied.
Also, we have introduced the condition under which edge regular cubic graph and totally edge regular cubic graph are equivalent.
In our future work, we are going to extend the properties of strongly edge regular cubic graph in matrix representation.
Kumar.
Rashmanlou.
Talebi, and F.
Mofidnakhaei Algorithm 1 Cubic digraphs in road networks 1: void cubic shortest path() 2: C = cubic set of crossings.
3: number of crossings = count(C).
4: R = Empty cubic set of roads.
5: for.
nt c = 0.
c < number of crossings .
c ){ for.
nt c0 = 0.
c0 < number of crossings .
c0 ){ if (C.
is adjacent to C.
){ fP R cc0 O min.
AAQ .
AAf Q .
P cc0 Ou max(Q .
Q .
0 ).
13: R = cubic set of edges.
14: R = cubic relation (Adjacency matrix of F y F).
15: WG = Weighted relation (Adjacency matrix of F y F).
16: no.
of Edges = Count(R).
17: for.
nt i=0 .
i < no.
of Edges .
i ){ 18: si = .
AAR )i 1 Oe (R )i 19: c = Adjacent from Node of Ri .
20: c = Adjacent from Node of Ri .
21: WRcc0 = si .
22: }
23: print WR 24: Calculated optimal path using WR 25: } REFERENCES