Graphs with many large degrees (Q5946758): Difference between revisions
From MaRDI portal
Set profile property. |
Created claim: Wikidata QID (P12): Q127363414, #quickstatements; #temporary_batch_1722364966119 |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(01)00049-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2034859580 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q127363414 / rank | |||
Normal rank |
Latest revision as of 21:04, 30 July 2024
scientific article; zbMATH DE number 1659505
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs with many large degrees |
scientific article; zbMATH DE number 1659505 |
Statements
Graphs with many large degrees (English)
0 references
20 January 2003
0 references
The author proves the following results: (1) Let \(k,n,\lambda\in\mathbb{N}\), \(\lambda\geq k-1\), and \(n\geq \lambda+1\). Then \[ (k,n,\lambda)= \min\Biggl\{\Biggl\lfloor{(n- k)(k-1)\over \lambda-k+1}\Biggr\rfloor, n-(\lambda- k+1)\Biggr\}. \] (The right-hand side is defined to be \(n-(\lambda-k+1)= n\) for \(\lambda=k-1\).) (2) Every nonempty graph \(G\) has a subgraph \(H\) with \(\delta(H)> \mu(G)/3\). (3) Every graph \(G\) satisfies \(\text{MAD}(G)\geq{2\over 3} \mu(G)\). That is, every graph \(G\) has a subgraph \(H\) with \(t(H)\geq {2\over 3}\mu(G)\). In general, for \(0\leq q< 1\), \(\text{MAD}(G)\geq {2-2q \over 2-q} \mu_q (G)\), and hence, if \(G\) is nonempty then \(\text{MMD}(G)> {1-q \over 2-q} \mu_q(G)\). (4) Every nonempty graph \(G\) has a subgraph \(H\) such that \(t(H)\geq{2\over 3} \mu(G)\) and \(\delta(H)>{1\over 2} t(H)\).
0 references
graph
0 references
large degree
0 references
minimal degree
0 references
median degree
0 references
subgraph
0 references