Degree distance of unicyclic and bicyclic graphs

Aleksandar Ili, Dragan Stevanovi, Lihua Feng, Guihai Yu, Peter Dankelmann

Research output: Contribution to journalArticlepeer-review

54 Citations (Scopus)

Abstract

Let G be a connected graph with vertex set V(G). The degree distance of G is defined as D′(G)=∑u,v⊆V(G)(degG(u)+degG(v))d(u,v), where degG(u) is the degree of vertex u, and d(u,v) denotes the distance between u and v. Here we characterize n-vertex unicyclic graphs with girth k, having minimum and maximum degree distance, respectively. Furthermore, we prove that the graph Bn, obtained from two triangles linked by a path, is the unique graph having the maximum degree distance among bicyclic graphs, which resolves a recent conjecture of Tomescu.

Original languageEnglish
Pages (from-to)779-788
Number of pages10
JournalDiscrete Applied Mathematics
Volume159
Issue number8
DOIs
Publication statusPublished - 28 Apr 2011
Externally publishedYes

Keywords

  • Bicyclic graph
  • Degree distance
  • Girth
  • Wiener index

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Degree distance of unicyclic and bicyclic graphs'. Together they form a unique fingerprint.

Cite this