Maximally edge-connected hypergraphs

Peter Dankelmann; Dirk Meierling

doi:10.1016/j.disc.2015.07.008

Maximally edge-connected hypergraphs

Peter Dankelmann, Dirk Meierling

Mathematics and Applied Mathematics

Ulm University

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

Abstract

Abstract The edge-connectivity of a connected graph or hypergraph is the minimum number of edges whose removal renders the graph or hypergraph, respectively, disconnected. The edge-connectivity of a (hyper) graph cannot exceed its minimum degree. For graphs, several sufficient conditions for equality of edge-connectivity and minimum degree are known. For example Chartrand (1966) showed that for every graph of order n and minimum degree at least (Formula presented.) its edge-connectivity equals its minimum degree. We show that this and some other well-known sufficient conditions generalise to hypergraphs.

Original language	English
Article number	10212
Pages (from-to)	33-38
Number of pages	6
Journal	Discrete Mathematics
Volume	339
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2015.07.008
Publication status	Published - 10 Aug 2016

Keywords

Connectivity
Edge-connectivity
Hypergraph
Maximally edge-connected

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2015.07.008

Cite this

@article{44b58a58b5754eb8bde49924d35889ff,

title = "Maximally edge-connected hypergraphs",

abstract = "Abstract The edge-connectivity of a connected graph or hypergraph is the minimum number of edges whose removal renders the graph or hypergraph, respectively, disconnected. The edge-connectivity of a (hyper) graph cannot exceed its minimum degree. For graphs, several sufficient conditions for equality of edge-connectivity and minimum degree are known. For example Chartrand (1966) showed that for every graph of order n and minimum degree at least (Formula presented.) its edge-connectivity equals its minimum degree. We show that this and some other well-known sufficient conditions generalise to hypergraphs.",

keywords = "Connectivity, Edge-connectivity, Hypergraph, Maximally edge-connected",

author = "Peter Dankelmann and Dirk Meierling",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2016",

month = aug,

day = "10",

doi = "10.1016/j.disc.2015.07.008",

language = "English",

volume = "339",

pages = "33--38",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Maximally edge-connected hypergraphs

AU - Dankelmann, Peter

AU - Meierling, Dirk

PY - 2016/8/10

Y1 - 2016/8/10

N2 - Abstract The edge-connectivity of a connected graph or hypergraph is the minimum number of edges whose removal renders the graph or hypergraph, respectively, disconnected. The edge-connectivity of a (hyper) graph cannot exceed its minimum degree. For graphs, several sufficient conditions for equality of edge-connectivity and minimum degree are known. For example Chartrand (1966) showed that for every graph of order n and minimum degree at least (Formula presented.) its edge-connectivity equals its minimum degree. We show that this and some other well-known sufficient conditions generalise to hypergraphs.

AB - Abstract The edge-connectivity of a connected graph or hypergraph is the minimum number of edges whose removal renders the graph or hypergraph, respectively, disconnected. The edge-connectivity of a (hyper) graph cannot exceed its minimum degree. For graphs, several sufficient conditions for equality of edge-connectivity and minimum degree are known. For example Chartrand (1966) showed that for every graph of order n and minimum degree at least (Formula presented.) its edge-connectivity equals its minimum degree. We show that this and some other well-known sufficient conditions generalise to hypergraphs.

KW - Connectivity

KW - Edge-connectivity

KW - Hypergraph

KW - Maximally edge-connected

UR - http://www.scopus.com/inward/record.url?scp=84938865964&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2015.07.008

DO - 10.1016/j.disc.2015.07.008

M3 - Article

AN - SCOPUS:84938865964

SN - 0012-365X

VL - 339

SP - 33

EP - 38

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

M1 - 10212

ER -

Maximally edge-connected hypergraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this