Geodesic
Triameter of Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 601-616.

Voir la notice de l'article provenant de la source Library of Science

In this paper, we study a new distance parameter triameter of a connected graph G, which is defined as maxd(u; v)+d(v;w)+d(u;w) : u; v;w ∈ V and is denoted by tr(G). We find various upper and lower bounds on tr(G) in terms of order, girth, domination parameters etc., and characterize the graphs attaining those bounds. In the process, we provide some lower bounds of (connected, total) domination numbers of a connected graph in terms of its triameter. The lower bound on total domination number was proved earlier by Henning and Yeo. We provide a shorter proof of that. Moreover, we prove Nordhaus-Gaddum type bounds on tr(G) and find tr(G) for some specific family of graphs.
Keywords: distance, radio k -coloring, Nordhaus-Gaddum bounds 
@article{DMGT_2021_41_2_a15,
     author = {Das, Angsuman},
     title = {Triameter of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {601--616},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a15/}
}
TY  - JOUR
AU  - Das, Angsuman
TI  - Triameter of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 601
EP  - 616
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a15/
LA  - en
ID  - DMGT_2021_41_2_a15
ER  - 
%0 Journal Article
%A Das, Angsuman
%T Triameter of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 601-616
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a15/
%G en
%F DMGT_2021_41_2_a15
Das, Angsuman. Triameter of Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 601-616. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a15/

[1] G. Chartrand, D. Erwin and P. Zhang, A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl. 43 (2005) 43–57.

[2] D. Cvetković and M. Petrić, A Table of connected graphs on six vertices, Discrete Math. 50 (1984) 37–49. doi:10.1016/0012-365X(84)90033-5

[3] P. Duchet and H. Meyniel, On Hadwiger's number and stability number, Ann. Discrete Math. 13 (1982) 71–74. doi:10.1016/S0304-0208(08)73549-7

[4] O. Favaron and D. Kratsch, Ratios of domination parameters, in: Advances in Graph Theory, V.R. Kulli, (Ed(s)), (Vishwa, Gulbarga, 1991) 173–182.

[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).

[6] S.T. Hedetniemi and R. Laskar, Connected domination in graphs, in: Graph Theory and Combinatorics, B. Bollobás (Ed(s)), (Academic Press, London 1984), 209–218.

[7] M.A. Henning and A. Yeo, A new lower bound for the total domination number in graphs proving a Graffiti.pc Conjecture, Discrete Appl. Math. 173 (2014) 45–52. doi:10.1016/j.dam.2014.03.013

[8] S.R. Kola and P. Panigrahi, A Lower bound for radio k-chromatic number of an arbitrary graph, Contrib. Discrete Math. 10 (2015) 45–56.

[9] M. Laurent, Graphic vertices of the metric polytope, Discrete Math. 151 (1996) 131–151. doi:10.1016/0012-365X(94)00091-V

[10] L. Saha and P. Panigrahi, Antipodal number of some powers of cycles, Discrete Math. 312 (2012) 1550–1557. doi:10.1016/j.disc.2011.10.032

[11] L. Saha and P. Panigrahi, A lower bound for radio k-chromatic number, Discrete Appl. Math. 192 (2015) 87–100. doi:10.1016/j.dam.2014.05.004

[12] U. Sarkar and A. Adhikari, On characterizing radio k-coloring problem by path covering problem, Discrete Math. 338 (2015) 615–620. doi:10.1016/j.disc.2014.11.014

[13] U. Sarkar and A. Adhikari, On relationship between Hamiltonian path and holes in L(3, 2, 1)-coloring of minimum span, Discrete Appl. Math. 222 (2017) 227–234. doi:10.1016/j.dam.2017.01.017

[14] D.B. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, 2001).

[15] List of small graphs. http://www.graphclasses.org/smallgraphs.html#nodes5 http://users.cecs.anu.edu.au/bdm/data/graphs.html

[16] SageMath. http://www.sagemath.org/