On a conjecture between Randic index and average distance of unicyclic graphs

Autor:	Zhifu You, Bolian Liu
Rok vydání:	2014
Předmět:	Combinatorics Discrete mathematics New digraph reconstruction conjecture Degree (graph theory) Graph power General Mathematics Shortest-path tree Neighbourhood (graph theory) Bound graph Wiener index Mathematics Vertex (geometry)
Zdroj:	Filomat. 28:767-773
ISSN:	2406-0933 0354-5180
DOI:	10.2298/fil1404767y
Popis:	The Randiindex R(G) of a graph G is defined as R(G) = P uv2E (d(u)d(v)) 1 2 , where the summation goes over all edges of G. In 1988, Fajtlowicz proposed a conjecture: For all connected graphs G with average distance ad(G), then R(G) ad(G). In this paper, we prove that this conjecture is true for unicyclic graphs. Let G = (V(G); E(G)) be a simple graph with n =jV(G)j vertices and m =jE(G)j vertices. A connected graph is a unicyclic graph if m = n. d(v) (or dv) denotes the degree of a vertex v. A vertex of degree one is called a leaf. Denote the number of leaves in G by n1. LetT (n; n1) andU(n; n1) be the sets of trees and unicyclic graphs with n vertices and n1 leaves, respectively. The distance dG(u; v) is the number of edges in a shortest path from u to v in G. And the average distance ad(G) of graph G is the average value of the distances between all pairs of vertices in G. Recall that the Wiener index W(G) is equal to P u;v2V d G(u; v). Then
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::d1dba12749b8c46bc19ff6e962af81a5 https://doi.org/10.2298/fil1404767y Zobrazit plný text záznamu