Graphs with many large degrees
The author proves the following results:NEWLINENEWLINENEWLINE(1) Let \(k,n,\lambda\in\mathbb{N}\), \(\lambda\geq k-1\), and \(n\geq \lambda+1\). Then NEWLINE\[NEWLINE(k,n,\lambda)= \min\Biggl\{\Biggl\lfloor{(n- k)(k-1)\over \lambda-k+1}\Biggr\rfloor, n-(\lambda- k+1)\Biggr\}.NEWLINE\]NEWLINE (The right-hand side is defined to be \(n-(\lambda-k+1)= n\) for \(\lambda=k-1\).)NEWLINENEWLINENEWLINE(2) Every nonempty graph \(G\) has a subgraph \(H\) with \(\delta(H)> \mu(G)/3\).NEWLINENEWLINENEWLINE(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)\).NEWLINENEWLINENEWLINE(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)\).
- Large Graphs with Given Degree and Diameter—Part I
- scientific article; zbMATH DE number 4059444
- Some large graphs with given degree and diameter
- Very large graphs
- Subgraphs with large degrees and girth
- scientific article; zbMATH DE number 4103105
- Large graphs with given degree and diameter. II
- scientific article; zbMATH DE number 861410
- On a problem of a. kotzig concerning factorizations of 4‐regular graphs
- Graphs with unavoidable subgraphs with large degrees
This page was built for publication: Graphs with many large degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946758)
