scientific article; zbMATH DE number 4122022

From MaRDI portal
Publication:4735210





[For the entire collection see Zbl 0673.00009.] Let \(G\) be a graph of order \(n\) with degree sequence \((d_1\;le d_2 \leq \ldots \leq d_n)\). Let \(D=\{i: d_i=d_j\) for some \(i\neq j\}\) (duplicated degrees) and \(S=\{1,\ldots,n\}-D\) (single degrees). Let \(D'\) be that proper subset of \(D\) which one obtains in choosing the first index associated with each duplicated degree. Finally let \(M=\{j: 0\leq j\leq n-1\) and \(j\neq d_i\) for any \(i\}\) (missing degrees). It is proved the following location of duplicated degrees: If \(d_i\in S\) for all \(i>k\), then \(k\geq (\sqrt{4(n-\delta)+1}+1)/2\) where \(\d elta =0\) for \(n\) even, and \(\delta =1\) for \(n\) odd, and this result is best possible. Let \(\Sigma D\) and \(\Sigma D'\) be the sum of the degrees indexed by each of the sets. There are given bounds for these numbers, e.g.: If \(G\) has no isolated vertices, then \(\Sigma D'\geq 1\) and \(\Sigma D\geq \frac{n+3}{3}\) and these bounds are sharp. Furthermore let \(\Sigma M\) be the sum of the elements in \(M\). For sufficiently large \(n\) one has \(\Sigma D'+\Sigma M\geq \frac{n^{2/3}}2\) and \(\Sigma D+\Sigma M\geq n/2+n^{2/3}/2\) and these bounds are sharp in order of magnitude.











This page was built for publication:

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