Bicyclic graphs with extremal cover cost

被引：3

作者：

Lu, Jian ^{[1
]}

Pan, Xiang-Feng ^{[2
]}

Liu, Huiqing ^{[1
]}

机构：

[1] Hubei Univ, Fac Math & Stat, Hubei Key Lab Appl Math, Wuhan 430062, Hubei, Peoples R China

[2] Anhui Univ, Sch Math Sci, Hefei 230601, Anhui, Peoples R China

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2021年 / 405卷

关键词：

Bicyclic graph; Expected hitting time; Cover cost;

D O I：

10.1016/j.amc.2021.126235

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The expected hitting time H-xy is the expected number of steps it takes for a random walk that starts at x to reach y . For a vertex x of G, the cover cost of x, denoted by CCG(x), is defined as the sum of the expected hitting time for a random walk starting at x to visit all vertices of G . In this paper, we first reveal a close connection between the cover cost and some related graph invariants of bicyclic graphs, and then present sharp bounds of CCG(x) among all bicyclic graphs of order n and characterize the corresponding extremal graphs. (C) 2021 Elsevier Inc. All rights reserved.

引用

页数：10

共 11 条

[1]

[Anonymous], 1991, J. Theoret. Probab

[2]

Bapat RB., 2018, GRAPHS MATRICES

[3]

Feng LH, 2014, ARS COMBINATORIA, V114, P33

[4] Hitting Times, Cover Cost, and the Wiener Index of a Tree [J].

Georgakopoulos, Agelos ;

Wagner, Stephan .

JOURNAL OF GRAPH THEORY, 2017, 84 (03) :311-326

[5]

Georgakopoulos Georgak A., ARXIV12066605MATHCO

[6]

Gutman I, 2012, TRANS COMB, V1, P27

[7] Further results on the expected hitting time, the cover cost and the related invariants of graphs [J].

Huang, Jing ;

Li, Shuchao ;

Xie, Zheng .

DISCRETE MATHEMATICS, 2019, 342 (01) :78-95

[8] RESISTANCE DISTANCE [J].

KLEIN, DJ ;

RANDIC, M .

JOURNAL OF MATHEMATICAL CHEMISTRY, 1993, 12 (1-4) :81-95

[9] Complete characterization of bicyclic graphs with minimal Kirchhoff index [J].

Liu, Jia-Bao ;

Pan, Xiang-Feng ;

Yu, Lei ;

Li, Dong .

DISCRETE APPLIED MATHEMATICS, 2016, 200 :95-107

[10] ON THE SUM OF ALL DISTANCES IN A GRAPH OR DIGRAPH [J].

PLESNIK, J .

JOURNAL OF GRAPH THEORY, 1984, 8 (01) :1-21

← 1 2 →