Labeling of Chain Bipartite Graphs
- PDF / 442,138 Bytes
- 3 Pages / 595.276 x 790.866 pts Page_size
- 22 Downloads / 254 Views
SHORT COMMUNICATION
Labeling of Chain Bipartite Graphs G. Sathiamoorthy1
Received: 27 May 2018 / Revised: 25 January 2020 / Accepted: 31 January 2020 Ó The National Academy of Sciences, India 2020
Abstract A chain bipartite graph is a graph whose graph vertices can be partitioned into n disjoint sets so that no two vertices within the same set are adjacent and only between any two sets edges are connected. Also, it is known by clustered bipartite graph. In this paper it is proved that chain bipartite graph satisfies graceful and a-labeling. Graceful labeling proves the uniqueness between and within clusters and improves in the distributed computing techniques to the solution of computationally intensive applications across networks of computers. Keywords Clustered bipartite graph Chain bipartite graph Graceful labeling a-Labeling Mathematics Subject Classification 05C78
Graphs considered in this paper are simple finite and undirected. In general G(V, E) denotes the graph G with vertex set V(G) and edge set E(G), such that jVðGÞj ¼ p vertices jEðGÞj ¼ q edges. A labeling of the vertices of G with the numbers from 0 to q is an injective map / : V ! f0; 1; . . .qg.
A graph G is graceful if there exists a labeling of its vertices such that the map g : E ! f1; 2; . . .qg given by gðuvÞ ¼ j/ðuÞ /ðvÞj, where u; v 2 V and uv 2 E is a bijection. A graph that admits graceful labeling is called graceful graph. The notation graceful labeling was introduced by Rosa [1] with the name b-valuation. An a-labeling (a-valuation) defined as graceful labeling with the additional property that there exists an integer k so that for each edge uv either /ðuÞ k\/ðvÞ or /ðvÞ k\/ðuÞ, other words minð/ðuÞ; /ðvÞÞ k\max ðð/ðuÞ; /ðvÞÞÞ. Gallian [2] gives the extensive survey of contributions to graph labeling of a variety of graphs. Several computers [3] acting together as one, each one monitoring the others and taking their services if any of them will fail. The complexity of the system must be software that should bother to monitor other machines on a network, know what services are running, those who are running, and what to do in case of a failure. Fault tolerance is achieved through hardware like raid systems, supplies and redundant boards, and fully connected network systems to provide alternative paths in the breaking of a link. This results the cluster computing architecture which is shown in Fig. 1. Graceful labeling gives the mathematical way of load balancing and faults tolerance to be achieved. Theorem 1 A clustered bipartite graph satisfies graceful and a-labeling.
& G. Sathiamoorthy [email protected] 1
Proof Consider n sets are denoted by Vi ðGÞ, Vk ðGÞ 2 V(G) where i is an odd index and k is an even index. Each set consists of mi vertices denoted by vij 2 VðGÞ, i ¼ 2r 1, 1 r nþ1 2 and j denote number of vertices 1 j mi within the set. Similarly ukx 2 VðGÞ; k ¼
SASTRA Deemed University, Thanjavur, India
123
G. Sathiamoorthy
Step 1 /ðv1j Þ ¼ q m3 ðj 1Þ; 1 j m1 :/ðu2x Þ ¼ 0 þ ðx 1Þðm
Data Loading...
