Document Type : Original paper

**Authors**

^{1}
Goverment College of Engineering, Tirunelveli

^{2}
Bharathiyar University

**Abstract**

Let $G = (V, E)$ be a simple connected graph of order $p$ and size $q$. A decomposition of a graph $G$ is a collection $\pi$ of edge-disjoint subgraphs $G_{1}, G_{2} ,\dots, G_{n}$ of $G$ such that every edge of $G$ belongs to exactly one $G_{i},(1\leq i\leq n)$. The decomposition $\pi=\{G_{1},G_{2},\dots,G_{n}\}$ of a connected graph $G$ is said to be a distinct edge geodetic decomposition if $g_{1}(G_{i})\neq g_{1}(G_{j}),(1\leq i\neq j\leq n)$. The maximum cardinality of $\pi$ is called the distinct edge geodetic decomposition number of $G$ and is denoted by $\pi_{dg_{1}}(G)$, where $g_{1}(G)$ is the edge geodetic number of $G$. Some general properties satisfied by this concept are studied. Connected graphs of $\pi_{dg_{1}}(G)\geq2$ are characterized and connected graphs of order $p$ with $\pi_{dg_{1}}(G)=p-2$ are characterized.

**Keywords**

- Edge geodetic number
- minimum edge geodetic set
- Distinct edge geodetic decomposition
- Distinct edge geodetic decomposition number
- Star decomposition

**Main Subjects**

[1] H. Abdollahzadeh Ahangar, S. Kosari, S.M. Sheikholeslami, and L. Volkmann, Graphs with large geodetic number, Filomat 29 (2015), no. 6, 1361–1368.

[2] H. Abdollahzadeh Ahangar and M. Najimi, Total restrained geodetic number of graphs, Iran. J. Sci. Technol. Trans. A Sci. 41 (2017), no. 2, 473–480.

[3] H. Abdollahzadeh Ahangar, V. Samodivkin, S.M. Sheikholeslami, and A. Khodkar, The restrained geodetic number of a graph, Bull. Malays. Math. Sci. Soc. 38 (2015), no. 3, 1143–1155.

[4] J.M. Aroca, A. Llad´o, and S. Slamin, On the ascending subgraph decomposition problem for bipartite graphs, Electron. Notes Discrete Math. 46 (2014), 19–26.

[5] M. Atici, On the edge geodetic number of a graph, Int. J. Comput. Math. 80 (2003), no. 7, 853–861.

[6] F. Buckley and F. Harary, Distance in Graphs, Addition-Wesley, Redwood City, CA, 1990.

[7] S. Dantas, F. Maffray, and A. Silva, 2K2-partition of some classes of graphs, Discrete Math. 160 (2012), no. 18, 2662–2668.

[8] F. Harary, Graph Theory, Narosa Publishing House, 1998.

[9] B. Jamison and S. Olariu, P-components and the homogeneous decomposition of graphs, SIAM J. Discrete Math. 8 (1995), no. 3, 448–463.

[10] Z. Jianqin, M. Kejie, and Z. Huishan, A proof of the Alavi conjecture on integer decomposition, Acta Math. Sinica 5 (1996), 636–641.

[11] J. John and D. Stalin, The edge geodetic self decomposition number of a graph, RAIRO Oper. Res., (in press).

[12] J. John and D. Stalin, Edge geodetic self-decomposition in graphs, Discrete Math. Algorithms Appl. 12 (2020), no. 5, 2050064.

[12] J. John and D. Stalin, Edge geodetic self-decomposition in graphs, Discrete Math. Algorithms Appl. 12 (2020), no. 5, 2050064.

[13] J. John, P.A.P. Sudhahar, and D. Stalin, On the (M, D)-number of a graph, Proyecciones J. Math. 38 (2019), no. 2, 255–266.

[14] K. Ma, H. Zhou, and J. Zhou, On the ascending star subgraph decomposition of star forests, Combinatorica 14 (1994), no. 3, 307–320.

[15] R.E. Mariano and S.R. Canoy Jr, Edge geodetic covers in graphs, Int. Math. Forum 4 (2009), no. 46, 2301–2310.

[16] M. Presler and M. Tarsi, On the decomposition of graphs into copies of P3 ∪tK2, Ars Combin. 35 (1993), 325–333.

[17] V. Samodivkin, On the edge geodetic and edge geodetic domination numbers of a graph, Commun. Comb. Optim. 5 (2019), no. 1, 41–54.

[18] A.P. Santhakumaran and J. John, Edge geodetic number of a graph, J. Discrete Math. Sci. Cryptogr. 10 (2007), no. 3, 415–432.

[19] A.P. Santhakumaran and J. John, The connected edge geodetic number of a graph, SCIENTIA Series A: Math. Sci. 17 (2009), 67–82.

[20] A.P. Santhakumaran and J. John, The upper edge geodetic number and the forcing edge geodetic number of a graph, Opuscula Math. 29 (2009), no. 4, 427–441.

[21] A.P. Santhakumaran and J. John, The upper connected edge geodetic number of a graph, Filomat 26 (2012), no. 1, 131–141.

December 2021

Pages 185-196