Distinct edge geodetic decomposition in graphs

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

Main Subjects

References

[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.
[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.
 
Communications in Combinatorics and Optimization
Volume 6, Issue 2
December 2021
Pages 185-196

Files

Share

How to cite

Statistics