On Triameter of a Graph
Öz
The triameter of a graph G=(V,E)is denoted by tr(G)and defined as the maximum value of d(u,v)+d(v,w)+d(w,u)over all u,v,w∈V. In the first two chapter the concept of triameter is first defined, and its historical development is briefly discussed in the first section. In the third section, improved upper bounds for the triameter of a graph are derived in terms of its order n and δ. If G is a graph with δ≥3 and girth(G)≥5, then tr(G)≤(3(n-2))/(δ-1)≤6n/(δ+1) was obtained. Furthermore, when G is a cubic Cayley graph of order n with girth(G)=4, tr(G)≤n<6n/(δ+1) holds, and for minimally connected graph G, it is shown that tr(G)≤6n/(δ+1). The fourth section, a characterization is provided for all graphs having triameter 4, 5, or 2n-3. Finally, in the sixth section, several open problems are proposed for future research.
Anahtar Kelimeler
Distance in Graphs, Diameter, Minimum degree
Destekleyen Kurum
The first author acknowledge the funding of DST-SERB-MATRICS Sanction no.MTR/2022/000020, Govt. of India. This work was also supported by TUBITAK, the Scientific and Technological Research Council of Turkey, under the program “2221-Fellowship for Visiting Professor/Scientists”.
Kaynakça
- A. Das, Trimester of graphs, Discussiones Mathematicae Graph Theory. 41(2) (2021), 601-616. doi:10.7151/dmgt.2212
- A. Hak, S. Kozerenko and B. Oliynyk, A note on the triameter of graphs, Discrete Applied Mathematics. 309 (2022), 278-284. doi:10.1016/j.dam.2021.12.011
- N. Akgüneş, Some graph parameters on the strong product of monogenic semigroup graphs. Balıkesir Üniversitesi Fen Bilimleri Enstitüsü Dergisi. 20 (1) (2018), 412-420. doi:10.25092/baunfbed.418449
- N. Akgunes, I.N. Cangul, A.S. Cevik, A note on the upper bound of average distance via irregularity index, in: Nonlinear systems and complexity, 2018: pp. 267–271. doi:10.1007/978-3-319-91065-9_14
- D. B. West, Introduction to Graph Theory, Prentice Hall, 2001.
- P. Erdos, J. Pach, R. Pollack and Z. Tuza, Radius, diameter, and minimum degree, Journal of Combinatorial Theory Series B. 47(1) (1989), 73-79. doi:10.1016/0095-8956(89)90066-X
- D.L. Powers, Some Hamiltonian Cayley Graphs, North-Holland Mathematics Studies. 115 (1985), 129-140. doi:10.1016/S0304-0208(08)73002-0
- R. Halin, A theorem on n-connected graphs, Journal of Combinatorial Theory. (7) (1969), 150-154. doi:10.1016/S0021-9800(69)80049-9
- S.T. Hedetniemi and R.C. Laskar, Connected domination in graphs, In: B. Bollobas (Ed.), Graph Theory and Combinatorics, Academic Press, 1984: pp.209-218.
- A.C. Malaravan and A.W. Baskar, A note on graph and its complement with specified properties: radius, diameter, center, and periphery, Discrete Mathematics, Algorithms and Applications. 11(2) (2019), 1950021. doi:10.1142/S1793830919500216