𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A remark on the number of vertices of degree k in a minimally k-edge-connected graph

✍ Scribed by Mao-cheng Cai

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
395 KB
Volume
104
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a minimally k-edge-connected simple graph and u*(G) be the number of vertices of degree k in G. proved that (i) uk(G) 2 l(jGl -1)/(2k + l)] + k + 1 for even k, and (ii) uI(G) 2 [lGl/(k + l)] + k for odd k 35 and u,(G) 2 lZlGl/(k + l)] + k -2 for odd k 27, where ICI denotes the number of vertices of G. In this paper we slightly improve the result for k being even, i.e., uJG) 2 [IGl/(k + 1)j + k if k 34 and u*(G) 2 [2(Gl/(k + l)! + k -2 if k 3 10.

πŸ“œ SIMILAR VOLUMES

The number of vertices of degree k in a
The number of vertices of degree k in a minimally k-edge-connected digraph
✍ Yuan Xu-dong; Kang Liying; Cai Mao-cheng πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 298 KB πŸ‘ 2 views

Let k be a positive integer, and D = (V (D), E(D)) be a minimally k-edge-connected simple digraph. We denote the outdegree and indegree of x ∈ V (D) by δ D (x) and ρ D (x), respectively. Let u + (D) denote the number of vertices W. Mader asked the following question in [Mader, in Paul Erdâs is Eigh

On the number of vertices of given degre
On the number of vertices of given degree in a random graph
✍ Zbigniew Palka πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 115 KB πŸ‘ 1 views

This note can be treated a s a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G E ?An, p) asymptotically has a nor

New bounds on the edge number of a k-map
New bounds on the edge number of a k-map graph
✍ Zhi-Zhong Chen πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 310 KB πŸ‘ 1 views

## Abstract It is known that for every integer __k__ β‰₯ 4, each __k__‐map graph with __n__ vertices has at most __kn__ βˆ’ 2__k__ edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for __k__ = 4, 5. We also show that this bound is not tight for large en