scientific article; zbMATH DE number 4122022
[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.
- Extension problems with degree bounds
- An inequality for degree sequences
- Maximizing Wiener index for trees with given vertex weight and degree sequences
- Not all simple looking degree sequence problems are easy
- An extremal problem on degree sequences of graphs
- Reduced criteria for degree sequences
- Bounds for elements of the degree sequence of an unknown vertex set in a balanced bipartite graph
- scientific article; zbMATH DE number 800099 (Why is no real title available?)
- scientific article; zbMATH DE number 810044 (Why is no real title available?)
- scientific article; zbMATH DE number 2187677 (Why is no real title available?)
- On An Extremal Problem Concerning Primitive Sequences
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)