Distinct edge geodetic decomposition in graphs

Document Type : Original paper


1 Goverment College of Engineering, Tirunelveli

2 Bharathiyar University


Let G=(V,E) be a simple connected graph of order p and size q. A decomposition of a graph G is a collection π of edge-disjoint subgraphs G_1,G_2,…,G_n of G such that every edge of G belongs to exactly one G_i,
(1≤i ≤n). The decomposition 〖π={G〗_1,G_2,…,G_n} of a connected graph
G is said to be a distinct edge geodetic decomposition if g_1 (G_i )≠g_1 (G_j ),
(1≤i≠j≤n). The maximum cardinality of π is called the distinct edge geodetic decomposition number of G and is denoted by π_dg1 (G), where g_1 (G) is the edge geodetic number of G. Some general properties satisfied by this concept are studied. Connected graphs which are edge geodetic decomposable are characterized. Connected distinct edge geodetic decomposable graphs of order p with π_dg1 (G)= p-2 are characterised.


Main Subjects