Name
Abstract | ||
|---|---|---|
Let
$$H=(V,E)$$
be a hypergraph, where V is a set of vertices and E is a set of non-empty subsets of V called edges. If all edges of H have the same cardinality r, then H is a r-uniform hypergraph; if E consists of all r-subsets of V, then H is a complete r-uniform hypergraph, denoted by
$$K_n^r$$
, where
$$n=|V|$$
. A hypergraph
$$H'=(V',E')$$
is called a subhypergraph of
$$H=(V,E)$$
if
$$V'\subseteq V$$
and
$$E'\subseteq E$$
. A r-uniform hypergraph
$$H=(V,E)$$
is vertex-k-maximal if every subhypergraph of H has vertex-connectivity at most k, but for any edge
$$e\in E(K_n^r)\setminus E(H)$$
,
$$H+e$$
contains at least one subhypergraph with vertex-connectivity at least
$$k+1$$
. In this paper, we first prove that for given integers n, k, r with
$$k,r\ge 2$$
and
$$n\ge k+1$$
, every vertex-k-maximal r-uniform hypergraph H of order n satisfies
$$|E(H)|\ge (^n_r)-(^{n-k}_r)$$
, and this lower bound is best possible. Next, we conjecture that for sufficiently large n, every vertex-k-maximal r-uniform hypergraph H on n vertices satisfies
$$|E(H)|\le (^n_r)-(^{n-k}_r)+(\frac{n}{k}-2)(^k_r)$$
, where
$$k,r\ge 2$$
are integers. And the conjecture is verified for the case
$$r>k$$
. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00373-019-02052-z | Graphs and Combinatorics |
Keywords | Field | DocType |
Vertex-connectivity, Vertex-k-maximal hypergraphs,
r-Uniform hypergraphs | Integer,Combinatorics,Vertex (geometry),Upper and lower bounds,Constraint graph,Hypergraph,Cardinality,Vertex connectivity,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 5 | 0911-0119 |
Citations | PageRank | References |
1 | 0.40 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yingzhi Tian | 1 | 20 | 9.28 |
| Hong-Jian Lai | 2 | 631 | 97.39 |
| Jixiang Meng | 3 | 353 | 55.62 |