Independence and average distance in graphs (Q1363759)

From MaRDI portal
Revision as of 23:16, 10 February 2024 by RedirectionBot (talk | contribs) (‎Removed claims)
scientific article
Language Label Description Also known as
English
Independence and average distance in graphs
scientific article

    Statements

    Independence and average distance in graphs (English)
    0 references
    0 references
    19 January 1998
    0 references
    Let \(G=(V,E)\) be a simple connected graph of order \(n\geq 2\) and let \(k\) be a positive integer. A subset \(X\) of \(V\) is \(k\)-independent if the distance between every two vertices of \(X\) is at least \(k+1\). The \(k\)-independence number of \(G\), \(I_k(G)\), is defined to be the maximum cardinality over all \(k\)-independent sets of \(G\). The average distance of \(G\) is \(\mu(G)=\sum_{x,y\in V} d(x,y)/{n\choose 2}\). A sharp upper bound for \(I_k(G)\) is obtained in terms of \(k\) and \(n\). Furthermore, a lower bound, also sharp, is derived for \(\mu(G)\) in relation to \(k\), \(n\), and \(I_k(G)\), thus generalizing results of \textit{F. R. K. Chung} [J. Graph Theory 12, No. 2, 229-235 (1988; Zbl 0644.05029] and \textit{P. Dankelman} [Discrete Appl. Math. 51, No. 1-2, 75-83 (1994; Zbl 0803.05020)].
    0 references
    independence number
    0 references
    distance
    0 references

    Identifiers