Average distance and domination number
type: Item
instance of: scholarly article
title: Average distance and domination number
zbMATH Open document ID: 0888.05024
DOI: 10.1016/S0166-218X(97)00067-X
author: Peter Dankelmann
published in: Discrete Applied Mathematics
publication date: 1998-01-26T00:00:00Z
full work available at URL: dam
review text: The average distance \(\mu(G)\) of a graph \(G\) with \(n\) vertices is obtained from the sum of distances \(d_G(x,y)\) for all ordered pairs \(x\), \(y\) of vertices of \(G\) by dividing by \(n(n-1)\). By \(\gamma(G)\) the domination number of \(G\) is denoted, i.e. the minimum number of vertices of a dominating set in \(G\). (A subset \(D\) of the vertex set of \(G\) is called dominating, if each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\).) The main results are formulated in two theorems which give upper bounds for \(\mu(G)\) in terms of \(n\) and \(\gamma(G)\). The first theorem holds for graphs with \(\gamma(G)\leq n/3\), the second for graphs with \(\gamma(G)\geq n/3\).
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1109898
zbMATH Keywords: average distance
zbMATH Keywords: domination number
zbMATH Keywords: dominating set
reviewed by: Bohdan Zelinka
describes a project that uses: GRAFFITI
MaRDI profile type: Publication
cites work: A lower bound on the average shortest path length in regular graphs
cites work: The average distance and the independence number
cites work: Computing the average distance of an interval graph
cites work: Average distance and independence number
cites work: The average Steiner distance of a graph
cites work: On the average Steiner distance of graphs with presribed properties
cites work: Mean distance in a graph
cites work: Distance in graphs
cites work: Q3781134
cites work: On graphs having domination number half their order
cites work: Q3807048
cites work: On the sum of all distances in a graph or digraph
cites work: Q3764187
cites work: Maximum number of edges in connected graphs with a given domination number
cites work: Maximum chromatic polynomials of 2‐connected graphs
cites work: ON DISTANCES IN CHROMATIC GRAPHS
cites work: Domination critical graphs
cites work: Q5606538
description: scientific article; zbMATH DE number 1109898