Comparative study of distance-based graph invariants
- PDF / 294,425 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 171 Views
Comparative study of distance-based graph invariants Hongzhuan Wang1 · Hongbo Hua1
· Maolin Wang1
Received: 21 January 2020 © Korean Society for Informatics and Computational Applied Mathematics 2020
Abstract The investigation on relationships between various graph invariants has received much attention over the past few decades, and some of these research are associated with Graffiti conjectures (Fajtlowicz and Waller in Congr Numer 60:187–197, 1987) or AutoGraphiX conjectures (Aouchiche et al. in: Liberti, Maculan (eds) Global optimization: from theory to implementation, Springer, New York, 2006). The reciprocal degree distance (RDD), the adjacent eccentric distance sum (AEDS), the average distance (AD) and the connective eccentricity index (CEI) are all distance-based graph invariants or topological indices, some of which found applications in Chemistry. In this paper, we investigate the relationship between RDD and other three graph invariants AEDS, CEI and AD. First, we prove that AEDS > RDD for any tree with at least three vertices. Then, we prove that RDD > CEI for all connected graphs with at least three vertices. Moreover, we prove that RDD > AD for all connected graphs with at least three vertices. As a consequence, we prove that AEDS > CEI and AEDS > AD for any tree with at least three vertices. Keywords Reciprocal degree distance · Adjacent eccentric distance sum · Average distance · Eccentric connectivity index · Tree · Connected graph Mathematics Subject Classification 05C35 · 05C12
1 Introduction Throughout this paper we consider only simple connected graphs. For a graph G = (V , E) with vertex set V = V (G) and edge set E = E(G), the degree of a vertex v in G, denoted by dG (v), is the number of edges incident with v. Denote by dG (u, v) the distance between vertices u and v in G. The eccentricity of a vertex v in a graph G is defined to be εG (v) = max{dG (u, v)|u ∈ V (G)}. If dG (u, v) = εG (v) for
B 1
Hongbo Hua [email protected] Faculty of Mathematics and Physics, Huaiyin Institute of Technology, Huai’an City 223003, People’s Republic of China
123
H. Wang et al.
some vertex u in G, then u is said to be an eccentric vertex of v. The diameter of a connected graph G is equal to max{εG (v)|v ∈ V (G)}, while the radius of a connected graph G is equal to min{εG (v)|v ∈ V (G)}. A path in a connected graph is said to be a diametrical path, if this path is of length equal to the diameter. A connected graph is said to be a tree if it contains no cycles. Let Pn , Sn , Cn and K n be the path, star, cycle and complete graph of order n, respectively. For a ≥ 1, b ≥ 1, let Sa+1 and Sb+1 be stars on a + 1 and b + 1 vertices, respectively. Then the double star Sa, b is just the tree obtained by connecting an edge between two centers of Sa+1 and Sb+1 . For other notation and terminology not defined here, the readers are referred to [6]. One of the oldest and well-studied distance-based graph invariants associated with a connected graph G is the Wiener number W (G), also termed as Wiener index (WI) in c
Data Loading...
