×

On the (reverse) cover cost of trees with some given parameters. (English) Zbl 1453.05122

Summary: For a connected graph \(G = ( V_G , E_G ) ,\) the cover cost of a vertex \(u\) in \(G\) is defined as \(C C_G ( u ) = \sum_{v \in V_G} H_{u v}\) and the reverse cover cost of a vertex \(v\) in \(G\) is defined as \(R C_G ( v ) = \sum_{u \in V_G} H_{u v} ,\) where \(H_{u v}\) is the expected hitting time for random walk beginning at \(u\) to visit \(v .\) These two parameters were introduced as tractable variants of cover time on a graph. In this paper, some extremal problems on the (reverse) cover cost of a vertex in a tree with given graph parameters are considered. Firstly, the sharp lower bound on the cover cost among all \(n\)-vertex trees with given diameter (resp. matching number, domination number, vertex bipartition) is established. Secondly, the sharp lower bound on the reverse cover cost among all \(n\)-vertex trees with given diameter (resp. matching number, domination number) is established. All the corresponding extremal graphs are identified, respectively. At last, the unique \(n\)-vertex tree with given number of leaves having the minimum cover cost (resp. reverse cover cost) is characterized.

MSC:

05C81 Random walks on graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Aldous, J. Fill, Reversible Markov chains and random walks on graphs, Available at http://statwww.berkeley.edu/users/aldous/RWG/book.html.
[2] Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A., On the power of randomization in on-line algorithms, Algorithmica, 11, 2-14 (1994) · Zbl 0784.68038
[3] Biggs, N. L., Potential theory on distance-regular graphs, (Cambridge Conference in Honour of Paul Erdós (1993)) · Zbl 0793.94007
[4] Bollobás, B., (Modern Graph Theory. Modern Graph Theory, Graduate Texts in Mathematics, vol. 184 (1998), Springer-Verlag: Springer-Verlag New York) · Zbl 0902.05016
[5] Bollobás, B.; Tyomkyn, M., Walks and paths in trees, J. Graph Theory, 70, 54-66 (2012) · Zbl 1242.05055
[6] Bondy, J. A.; Murty, U. S.R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 244 (2008), Springer) · Zbl 1134.05001
[7] Brightwell, G.; Winkler, P., Extremal cover times for random walks on trees, J. Graph Theory, 14, 547-554 (1990) · Zbl 0743.05015
[8] Buckley, F.; Harary, F., Distance in Graphs (1990), Addison-Wesley: Addison-Wesley Redwood · Zbl 0688.05017
[9] Chang, X.; Xu, H., Random walks on complete multipartite graphs, Pure Appl. Math. Q., 11, 393-402 (2015) · Zbl 1365.05266
[10] Chang, X.; Xu, H., Chung-Yau invariants and graphs with symmetric hitting times, J. Graph Theory, 85, 691-705 (2017) · Zbl 1367.05198
[11] Chang, X.; Xu, H.; Yau, S.-T., Spanning trees and random walks on weighted graphs, Pacific J. Math., 273, 241-255 (2015) · Zbl 1307.05207
[12] Chen, H. Y.; Zhang, F. J., The expected hitting times for graphs with cutpoints, Statist. Probab. Lett., 66, 9-17 (2004) · Zbl 1113.60046
[13] Csikvári, P., On a poset of trees, Combinatorica, 30, 2, 125-137 (2010) · Zbl 1224.05093
[14] Devroye, L.; Sbihi, A., Random walks on highly symmetric graphs, J. Theoret. Probab., 4, 497-514 (1990) · Zbl 0711.60068
[15] Dobrynin, A. A.; Entringer, R.; Gutman, I., Wiener index of trees: Theory and applications, Acta Appl. Math., 66, 3, 211-249 (2001) · Zbl 0982.05044
[16] Doyle, P. G.; Snell, J. L., Random walks and electric networks, (Carus Mathematical Monographs, vol. 22 (1984), Mathematical Association of America: Mathematical Association of America District of Columbia) · Zbl 0583.60065
[17] Du, Z. B., Wiener indices of trees and monocyclic graphs with given bipartition, Int. J. Quantum Chem., 112, 1598-1605 (2012)
[18] Entringer, R. C.; Jackson, D. E.; Snyder, D. A., Distance in graphs, Czechoslovak Math. J., 26, 283-296 (1976) · Zbl 0329.05112
[19] Feige, U., Collecting coupons on trees and the analysis of random walks, Comput. Complexity, 6, 341-356 (1996) · Zbl 0897.05082
[20] Geng, X. Y.; Li, S. C.; Zhang, M., Extremal values on the eccentric distance sum of trees, Discrete Appl. Math., 161, 2427-2439 (2013) · Zbl 1285.05099
[21] Georgakopoulos, A., A tractable variant of cover time (2012), arXiv:1206.6605 [math.CO]
[22] Georgakopoulos, A.; Wagner, S., Hitting times, cover cost, and the Wiener index of a tree, J. Graph Theory, 84, 311-326 (2017) · Zbl 1359.05113
[23] Gutman, I., A property of the Wiener number and its modifications, Indian J. Chem., 36A, 128-132 (1997)
[24] Gutman, I.; Klavžar, S.; Mohar, B., Fifty years of the Wiener index, MATCH Commun. Math. Comput. Chem., 35, 1-259 (1997)
[25] Gutman, I.; Polansky, O. E., Mathematical Concepts in Organic Chemistry (1986), Springer: Springer Berlin · Zbl 0657.92024
[26] Huang, J.; Li, S. C.; Xie, Z., Further results on the expected hitting time, the cover cost and the related invariants of graphs, Discrete Math., 342, 78-95 (2019) · Zbl 1400.05218
[27] Ilić, A., Trees with minimal Laplacian coefficients, Comput. Math. Appl., 59, 2776-2783 (2010) · Zbl 1193.05060
[28] Kelmans, A. K., Comparison of graphs by their number of spanning trees, Discrete Math., 16, 241-261 (1976) · Zbl 0346.05101
[29] Kelmans, A. K., Operations over graphs that increase the number of their trees (in Russian), (Studies in Discrete Optimization (1976), Nauka: Nauka Moscow), 406-424
[30] Knor, M.; Škrekovski, R.; Tepeh, A., Orientations of graphs with maximum Wiener index, Discrete Appl. Math., 211, 121-129 (2016) · Zbl 1348.05066
[31] Li, S. C.; Meng, X., Four edge-grafting theorems on the reciprocal degree distance of graphs and their applications, J. Comb. Optim., 30, 468-488 (2015) · Zbl 1327.05092
[32] Li, S. C.; Song, Y. B., On the sum of all distances in bipartite graphs, Discrete Appl. Math., 169, 176-185 (2014) · Zbl 1288.05072
[33] Li, S. C.; Wang, S. J., Extremal cover cost and reverse cover cost of trees with given segment sequence, Discrete Math., 343, Article 111791 pp. (2020) · Zbl 1434.05138
[34] Li, S. C.; Zhang, H. H., Some extremal properties of the multiplicatively weighted Harary index of a graph, J. Comb. Optim., 31, 961-978 (2016) · Zbl 1336.05103
[35] Lovász, L., Random walks on graphs: a survey, (Combinatorics Paul Erdós is Eighty, Vol. 2 (1993), Bolyai Soc. Math. Stud.), 1-46, (1)
[36] Mukwembi, S.; Vetrík, T., Wiener index of trees of given order and diameter at most 6, Bull. Aust. Math. Soc., 89, 379-396 (2014) · Zbl 1292.05102
[37] Nash-Williams, C. St. J.A., Random walk and electric current networks, Math. Proc. Camb. Phil. Soc., 55, 181-194 (1959) · Zbl 0100.13602
[38] Palacios, J. L., On hitting times of random walks on trees, Statist. Probab. Lett., 79, 234-236 (2009) · Zbl 1168.90003
[39] Palacios, J. L.; Renom, J. M.; Berrizbeitia, P., Random walks on edge transitive graphs (II), Statist. Probab. Lett., 43, 25-32 (1999) · Zbl 0942.60030
[40] Patel, R.; Carron, A.; Bullo, F., The hitting time of multiple random walks, SIAM J. Matrix Anal. Appl., 37, 3, 933-954 (2016) · Zbl 1344.60043
[41] Tetali, P., Random walks and the effective resistance of networks, J. Theoret. Probab., 4, 101-109 (1991) · Zbl 0722.60070
[42] Wang, S. J.; Guo, X. F., Trees with the extremal Wiener indices, MATCH Commun. Math. Comput. Chem., 69, 609-622 (2008) · Zbl 1199.05099
[43] Wiener, H., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, 17-20 (1947)
[44] Xu, H.; Yau, S. T., Discrete Green’s functions and random walks on graphs, J. Combin. Theory Ser. A, 120, 483-499 (2013) · Zbl 1256.05225
[45] Zelinka, B., Medians and peripherians of trees, Arch. Math. (Brno), 4, 87-95 (1968) · Zbl 0206.26105
[46] Zhang, H. H.; Chen, J.; Li, S. C., On the quotients between the (revised) szeged index and Wiener index of graphs, Discrete Math. Theor. Comput. Sci., 19, 1 (2017), #12 · Zbl 1400.05076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.