The edge-to-edge geodetic domination number of a graph

Authors

DOI:

https://doi.org/10.22199/issn.0717-6279-4057

Keywords:

Edge-to-edge geodetic domination number, Edge-to-edge geodetic number, Edge domination number, Geodetic number

Abstract

Let G = (V, E) be a connected graph with at least three vertices. A set S Í E is called an edge-to-edge geodetic dominating set of G if S is both an edge-to-edge geodetic set of G and an edge dominating set of G. The edge-to- edge geodetic domination number ¡gee(G) of G is the minimum cardinality of its edge-to-edge geodetic dominating sets and any edge-to-edge geodetic dominating set of minimum cardinality is said to be a gee- set of G. Some general properties satisfied by this concept are studied. Connected graphs of size m?2 with edge-to-geodetic domination number 2 or m or m-1 are charaterized. We proved that if G is a connected graph of size m ? 3 and G­ is also connected,then 4 ?¡gee(G) + ¡gee(G­) ? 2m -2. Moreover we characterized graphs for which the lower and the upper bounds are sharp. It is shown that, for every pair of positive integers a and b with 2 ?a ? b, there exists a connected graph G with gee(G) = a and ¡gee(G) = b. Also it is shown that, for every pair of positive integers a and b with 2 < a ? b, there exists a connected graph G with ¡e(G) = a and¡ gee(G) = b, where ¡e(G) is the edge domination number of G and gee(G) is the edge-to-edge geodetic number of G.

Author Biographies

J. John, Government College of Engineering

Dept. of Mathematics.

V. Sujin Flower, Holy Cross College (Autonomous)

Dept. of Mathematics.

References

M. Antony and A. L. Merlin Sheela, “The edge-to-edge geodetic number of a graph”, Journal of applied science and computation, vol. 6, no. 5, pp. 1954-1962, 2019.[On line]. Available: https://bit.ly/2Qd6r71

S. Arumugam and S. Velammal, “Edge domination in graphs”, Taiwanese journal of mathematics, vol. 2, no. 2, pp. 173-179, 1998, doi: 10.11650/twjm/1500406930

B. Xu, “On edge domination number of graphs”, Discrete mathematics, vol. 294, no. 3, pp. 311-316, 2005, doi: 10.1016/j.disc.2004.11.008

S. Beulah Samli and S. Robinson Chellathurai, “Geo chromatic number of a graph”, International Journal of Scientific Research in Mathematical and Statistical Sciences, vol. 5, no. 6, pp. 259-264, 2018, doi: 10.26438/ijsrmss/v5i6.259264

S. Beulah Samli. J. John , and S. Robinson Chellathurai, “The double geo chromatic number of a graph”, Bulletin of the International Mathematical Virtual Institute , vol. 11, no. 1, pp. 25-38, 2021. [On line]. Available: https://bit.ly/3v16C3Y

G. Chartrand, F. Harary, and P. Zhang, “On the geodetic number of a graph”, Networks, vol. 39, no. 1, pp. 1-6, 2002, doi: 10.1002/net.10007

G. Chartrand, E. M. Palmer, and P. Zhang, “The geodetic number of a graph: a survey”, Congressus numerantium, vol. 156, pp. 37-58, 2002.

R. D. Dutton and R. C. Brigham, “An external problem for edge domination insensitive graphs”, Discrete applied mathematics, vol. 20, no. 3, pp. 113-125, 1988, doi: 10.1016/0166-218X(88)90058-3

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of domination in graphs. New York, NY: M. Dekker, 1998.

A. Hansberg, and L. Volkmann, “On the geodetic and geodetic domination numbers of a graph”, Discrete mathematics, vol. 310, no. 15-16, pp. 2140-2146, 2010, doi: 10.1016/j.disc.2010.04.013

J. John, G. Edwin, and P. A. P. Sudhahar, “The Steiner domination number of a graph”, International journal of mathematics and computer applications research, vol. 3, no. 3, pp. 37-42, 2013. [On line]. Available: https://bit.ly/3uXvauQ

J. John and N. Arianayagam, “The detour domination number of a graph”, Discrete mathematics, algorithms and applications, vol. 9, no. 1, Art. ID. 1750006, 2017, doi: 10.1142/S1793830917500069

J. John, P. A. P. Sudhahar, and D. Stalin, “On the (M, D) number of a graph”, Proyecciones (Antofagasta), vol. 38, no. 2, pp. 255-266, 2019, doi: 10.4067/S0716-09172019000200255

J. John and D. Stalin, “Edge geodetic self-decomposition in graphs”, Discrete mathematics, algorithms and applications, vol. 12, no. 5, Art. ID. 2050064,2020, doi: 10.1142/S1793830920500640

J. John and D. Stalin, “The edge geodetic self decomposition number of a graph”, RAIRO - Operations Research, vol. 55, 2021, doi: 10.1051/ro/2020073

S. Mitchell and S. T. Hedetniemi, “Edge domination in trees”, Congressus numerantium, vol. 19, pp. 489-509, 1977.

M. N. S. Paspasan and S. R. Canoy Jr, “Edge domination and total edge domination in the join of graphs”, Applied mathematical science, vol. 10, no. 21, pp. 1077-1086, 2016, doi: 10.12988/AMS.2016.6130

M. N. S. Paspasan and S. R. Canoy Jr, “Edge domination in lexico and cartesian products of graphs”, Far east journal of mathematical science, vol. 102, no. 2, pp. 337-347, 2017, doi: 10.17654/MS102020337

M. Hajian, M. A. Henning, and N. J. Rad, “A new lower bound on the domination number of a graph”, Journal of combinatorial optimization, vol. 38, no. 3, pp. 721–738, 2019, doi: 10.1007/s10878-019-00409-x

P. Gupta, “Domination in graph with application”, Paripex indian journal of research, vol. 2, no. 3, pp. 115-117, 2013. [On line]. Available: https://bit.ly/3x7pEru

A. P. Santhakumaran and J. John, “On the edge-to-vertex geodetic number of a graph”, Miskolc mathematical notes, vol. 13, no. 1, pp. 107–119, 2012, doi: 10.18514/MMN.2012.353

A. P. Santhakumaran and J. John, “The upper connected edge geodetic number of a graph”, Filomat, vol. 26, no. 1, pp. 131-141, 2012, doi: 10.2298/FIL1201131S

D. Stalin and J. John, “Edge geodetic dominations in graphs”, International journal of pure and applied mathematics, vol. 116, no. 22, pp. 31-40, 2017. [On line]. Available: https://bit.ly/3dtlDpB

S. Sujitha, J. John, and A. Vijayan, “Extreme edge-to-vertex geodesic graphs”, International journal of mathematics research, vol. 6, no. 3, pp. 279-288, 2014.[On line]. Available: https://bit.ly/3srbXjr

S. Sujitha, J. John, and A. Vijayan, “The forcing edge-to-vertex geodetic number of a graph”, International journal of pure and applied mathematics, vol. 103, no. 1, 2015, pp. 109-121, 2015, doi: 10.12732/ijpam.v103i1.9

V. R. Sunil Kumar and J. John, “The total detour domination number of a graph”, Infokara research, vol. 8, no. 8, pp. 434-440, 2019. [On line]. Available: https://bit.ly/3mWBFeJ

F-H. Wang , Y-L. Wang, and J-M. ChangJ, “The lower and upper forcing geodetic numbers of blockcactus graphs”, European journal of operational research, vol. 175, no. 1, pp. 238-245, 2006, doi: 10.1016/j.ejor.2005.04.026

M. Yannakakis and F. Gavril, “Edge dominating sets in graphs”, SIAM journal on applied mathematics, vol. 38, no. 3, pp. 364-372, 1980, doi: 10.1137/0138030

Published

2021-04-27

How to Cite

[1]
J. John and V. Sujin Flower, “The edge-to-edge geodetic domination number of a graph”, Proyecciones (Antofagasta, On line), vol. 40, no. 3, pp. 635-658, Apr. 2021.

Issue

Section

Artículos