The Steiner k-Wiener index of graphs with given minimum degree

DOI10.1016/J.DAM.2019.05.015MaRDI QIDQ2274075zbMATH OpenOpenAlexFDO

Authors Peter Dankelmann

Publication date 19 September 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.04571

zbMATH Keywords

Steiner distanceWiener indextransmissionaverage distanceSteiner Wiener indexaverage Steiner distance

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40)

Abstract: Let $G$ be a connected graph. The Steiner distance $d(S)$ of a set $S$ of vertices is the minimum size of a connected subgraph of $G$ containing all vertices of $S$. For $kinmathbbN$, the Steiner $k$-Wiener index $S{W}_k(G)$ is defined as $su{m}_{S}d(S)$, where the sum is over all $k$-element subsets of the vertex set of $G$. The average Steiner $k$-distance $m{u}_k(G)$ of $G$ is defined as $$. In this paper we prove upper bounds on the Steiner Wiener index and the average Steiner distance of graphs with given order $n$ and minimum degree $delta$. Specifically we show that $$, and that $m{u}_k(G)leqfrack-1k+1frac3ndelta+1+O(1)$. We improve this bound for triangle-free graphs to $$, and $m{u}_k(G)leqfrack-1k+1frac2ndelta+O(1)$. All bounds are best possible.

Recommendations

• The upper bounds on the Steiner \(k\)-Wiener index in terms of minimum and maximum degrees
• The Steiner Wiener index of a graph
• Steiner Wiener index and connectivity of graphs
• Bounds on the Steiner-Wiener index of graphs
• Inverse problem on the Steiner Wiener index

Cites work

• scientific article; zbMATH DE number 4173028 (Why is no real title available?)
• scientific article; zbMATH DE number 5015716 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• A class of trees and its Wiener index
• A sharp lower bound on Steiner Wiener index for trees with given diameter
• All but 49 numbers are Wiener indices of trees
• Average Distance and Edge-Connectivity I
• Average Distance and Edge-Connectivity II
• Average distance and vertex-connectivity
• Average distance, minimum degree, and spanning trees
• Distance in graphs
• Inverse problem on the Steiner Wiener index
• Mathematical aspects of Wiener index
• Mean distance and minimum degree
• Mean distance in a graph
• Molecular graphs and the inverse Wiener index problem
• Nordhaus-Gaddum-type results for the Steiner Wiener index of graphs
• On Wiener index of common neighborhood graphs
• On maximum Wiener index of trees and graphs with given radius
• On the average Steiner distance of graphs with presribed properties
• On the sum of all distances in a graph or digraph
• On the sum of all distances in composite graphs
• Steiner Wiener index of graph products
• Steiner diameter of 3, 4 and 5-connected maximal planar graphs
• Steiner distance in graphs
• The Steiner Wiener index of a graph
• The Steiner diameter of a graph with prescribed girth
• The average Steiner distance of a graph
• Topology in chemistry. Discrete mathematics in molecules.
• Upper bounds on the Steiner diameter of a graph
• Using minimum degree to bound average distance
• Wiener index in weighted graphs via unification of \(\varTheta^\ast\)-classes
• Wiener index of trees of given order and diameter at most 6

Cited in

(8)

• A note on the Steiner \(k\)-radius and Steiner \(k\)-diameter
• Steiner diameter, maximum degree and size of a graph
• Bounding the \(k\)-Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence
• The edge-Wiener index of zigzag nanotubes
• Bounds on the Steiner-Wiener index of graphs
• The upper bounds on the Steiner \(k\)-Wiener index in terms of minimum and maximum degrees
• Steiner Wiener index and connectivity of graphs
• Minimum Wiener index of triangulations and quadrangulations

Describes a project that uses

Uses Software

• GRAFFITI

This page was built for publication: The Steiner \(k\)-Wiener index of graphs with given minimum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274075)