K-edge-connected Graph - Relation To Minimum Vertex Degree

Relation To Minimum Vertex Degree

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph G = (E,V) is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex vV. Obviously, deleting all edges incident to a vertex, v, would then disconnect v from the graph.

Read more about this topic:  K-edge-connected Graph

Famous quotes containing the words relation to, relation, minimum and/or degree:

    The foregoing generations beheld God and nature face to face; we, through their eyes. Why should not we also enjoy an original relation to the universe? Why should not we have a poetry and philosophy of insight and not of tradition, and a religion by revelation to us, and not the history of theirs?
    Ralph Waldo Emerson (1803–1882)

    To be a good enough parent one must be able to feel secure in one’s parenthood, and one’s relation to one’s child...The security of the parent about being a parent will eventually become the source of the child’s feeling secure about himself.
    Bruno Bettelheim (20th century)

    After decades of unappreciated drudgery, American women just don’t do housework any more—that is, beyond the minimum that is required in order to clear a path from the bedroom to the front door so they can get off to work in the mourning.
    Barbara Ehrenreich (20th century)

    There are no ninety degree angles in the Garden of Delight.
    Mason Cooley (b. 1927)