The Bounds of the Edge Number in Generalized Hypertrees
A hypergraph <inline-formula> <math display="inline"> <semantics> <mrow> <mi>H</mi> <mo>=</mo> <mo>(</mo> <mi>V</mi> <mo>,</mo> <mi>ε</mi> <mo>)</mo> </mrow> </sema...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-12-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/7/1/2 |
| _version_ | 1819089740158205952 |
|---|---|
| author | Ke Zhang Haixing Zhao Zhonglin Ye Yu Zhu Liang Wei |
| author_facet | Ke Zhang Haixing Zhao Zhonglin Ye Yu Zhu Liang Wei |
| author_sort | Ke Zhang |
| collection | DOAJ |
| description | A hypergraph <inline-formula> <math display="inline"> <semantics> <mrow> <mi>H</mi> <mo>=</mo> <mo>(</mo> <mi>V</mi> <mo>,</mo> <mi>ε</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> is a pair consisting of a vertex set <inline-formula> <math display="inline"> <semantics> <mrow> <mi>V</mi> </mrow> </semantics> </math> </inline-formula>, and a set <inline-formula> <math display="inline"> <semantics> <mi>ε</mi> </semantics> </math> </inline-formula> of subsets (the hyperedges of <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula>) of <inline-formula> <math display="inline"> <semantics> <mi>V</mi> </semantics> </math> </inline-formula>. A hypergraph <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> is <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform if all the hyperedges of <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> have the same cardinality <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>. Let <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> be an <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform hypergraph, we generalize the concept of trees for <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform hypergraphs. We say that an <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform hypergraph <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> is a generalized hypertree (<inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> </mrow> </semantics> </math> </inline-formula>) if <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> is disconnected after removing any hyperedge <inline-formula> <math display="inline"> <semantics> <mi>E</mi> </semantics> </math> </inline-formula>, and the number of components of <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> <mo>−</mo> <mi>E</mi> </mrow> </semantics> </math> </inline-formula> is a fixed value <inline-formula> <math display="inline"> <semantics> <mrow> <mi>k</mi> <mo> </mo> <mo stretchy="false">(</mo> <mn>2</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula>. We focus on the case that <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> <mo>−</mo> <mi>E</mi> </mrow> </semantics> </math> </inline-formula> has exactly two components. An edge-minimal <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> </mrow> </semantics> </math> </inline-formula> is a <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> </mrow> </semantics> </math> </inline-formula> whose edge set is minimal with respect to inclusion. After considering these definitions, we show that an <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> </mrow> </semantics> </math> </inline-formula> on <inline-formula> <math display="inline"> <semantics> <mi>n</mi> </semantics> </math> </inline-formula> vertices has at least <inline-formula> <math display="inline"> <semantics> <mrow> <mn>2</mn> <mi>n</mi> <mo>/</mo> <mo stretchy="false">(</mo> <mi>r</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula> edges and it has at most <inline-formula> <math display="inline"> <semantics> <mrow> <mi>n</mi> <mo>−</mo> <mi>r</mi> <mo>+</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> edges if <inline-formula> <math display="inline"> <semantics> <mrow> <mi>r</mi> <mo>≥</mo> <mn>3</mn> <mrow> <mo> </mo> <mi>and</mi> <mo> </mo> </mrow> <mi>n</mi> <mo>≥</mo> <mn>3</mn> </mrow> </semantics> </math> </inline-formula>, and the lower and upper bounds on the edge number are sharp. We then discuss the case that <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> <mo>−</mo> <mi>E</mi> </mrow> </semantics> </math> </inline-formula> has exactly <inline-formula> <math display="inline"> <semantics> <mrow> <mi>k</mi> <mo> </mo> <mo stretchy="false">(</mo> <mn>2</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>r</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula> components. |
| first_indexed | 2024-12-21T22:12:44Z |
| format | Article |
| id | doaj.art-685c14448fa24b0499678ac887c5652a |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-12-21T22:12:44Z |
| publishDate | 2018-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-685c14448fa24b0499678ac887c5652a2022-12-21T18:48:32ZengMDPI AGMathematics2227-73902018-12-0171210.3390/math7010002math7010002The Bounds of the Edge Number in Generalized HypertreesKe Zhang0Haixing Zhao1Zhonglin Ye2Yu Zhu3Liang Wei4School of Computer, Qinghai Normal University, Xining 810008, ChinaSchool of Computer, Qinghai Normal University, Xining 810008, ChinaKey Laboratory of Tibetan Information Processing and Machine Translation in QH, Xining 810008, ChinaSchool of Computer, Qinghai Normal University, Xining 810008, ChinaSchool of mathematics and statistics, Qinghai Normal University, Xining 810008, ChinaA hypergraph <inline-formula> <math display="inline"> <semantics> <mrow> <mi>H</mi> <mo>=</mo> <mo>(</mo> <mi>V</mi> <mo>,</mo> <mi>ε</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> is a pair consisting of a vertex set <inline-formula> <math display="inline"> <semantics> <mrow> <mi>V</mi> </mrow> </semantics> </math> </inline-formula>, and a set <inline-formula> <math display="inline"> <semantics> <mi>ε</mi> </semantics> </math> </inline-formula> of subsets (the hyperedges of <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula>) of <inline-formula> <math display="inline"> <semantics> <mi>V</mi> </semantics> </math> </inline-formula>. A hypergraph <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> is <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform if all the hyperedges of <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> have the same cardinality <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>. Let <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> be an <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform hypergraph, we generalize the concept of trees for <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform hypergraphs. We say that an <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform hypergraph <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> is a generalized hypertree (<inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> </mrow> </semantics> </math> </inline-formula>) if <inline-formula> <math display="inline"> <semantics> <mi>H</mi> </semantics> </math> </inline-formula> is disconnected after removing any hyperedge <inline-formula> <math display="inline"> <semantics> <mi>E</mi> </semantics> </math> </inline-formula>, and the number of components of <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> <mo>−</mo> <mi>E</mi> </mrow> </semantics> </math> </inline-formula> is a fixed value <inline-formula> <math display="inline"> <semantics> <mrow> <mi>k</mi> <mo> </mo> <mo stretchy="false">(</mo> <mn>2</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula>. We focus on the case that <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> <mo>−</mo> <mi>E</mi> </mrow> </semantics> </math> </inline-formula> has exactly two components. An edge-minimal <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> </mrow> </semantics> </math> </inline-formula> is a <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> </mrow> </semantics> </math> </inline-formula> whose edge set is minimal with respect to inclusion. After considering these definitions, we show that an <inline-formula> <math display="inline"> <semantics> <mi>r</mi> </semantics> </math> </inline-formula>-uniform <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> </mrow> </semantics> </math> </inline-formula> on <inline-formula> <math display="inline"> <semantics> <mi>n</mi> </semantics> </math> </inline-formula> vertices has at least <inline-formula> <math display="inline"> <semantics> <mrow> <mn>2</mn> <mi>n</mi> <mo>/</mo> <mo stretchy="false">(</mo> <mi>r</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula> edges and it has at most <inline-formula> <math display="inline"> <semantics> <mrow> <mi>n</mi> <mo>−</mo> <mi>r</mi> <mo>+</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> edges if <inline-formula> <math display="inline"> <semantics> <mrow> <mi>r</mi> <mo>≥</mo> <mn>3</mn> <mrow> <mo> </mo> <mi>and</mi> <mo> </mo> </mrow> <mi>n</mi> <mo>≥</mo> <mn>3</mn> </mrow> </semantics> </math> </inline-formula>, and the lower and upper bounds on the edge number are sharp. We then discuss the case that <inline-formula> <math display="inline"> <semantics> <mrow> <mi>G</mi> <mi>H</mi> <mi>T</mi> <mo>−</mo> <mi>E</mi> </mrow> </semantics> </math> </inline-formula> has exactly <inline-formula> <math display="inline"> <semantics> <mrow> <mi>k</mi> <mo> </mo> <mo stretchy="false">(</mo> <mn>2</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>r</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula> components.https://www.mdpi.com/2227-7390/7/1/2hypergraphgeneralized hypertreeboundcomponent |
| spellingShingle | Ke Zhang Haixing Zhao Zhonglin Ye Yu Zhu Liang Wei The Bounds of the Edge Number in Generalized Hypertrees Mathematics hypergraph generalized hypertree bound component |
| title | The Bounds of the Edge Number in Generalized Hypertrees |
| title_full | The Bounds of the Edge Number in Generalized Hypertrees |
| title_fullStr | The Bounds of the Edge Number in Generalized Hypertrees |
| title_full_unstemmed | The Bounds of the Edge Number in Generalized Hypertrees |
| title_short | The Bounds of the Edge Number in Generalized Hypertrees |
| title_sort | bounds of the edge number in generalized hypertrees |
| topic | hypergraph generalized hypertree bound component |
| url | https://www.mdpi.com/2227-7390/7/1/2 |
| work_keys_str_mv | AT kezhang theboundsoftheedgenumberingeneralizedhypertrees AT haixingzhao theboundsoftheedgenumberingeneralizedhypertrees AT zhonglinye theboundsoftheedgenumberingeneralizedhypertrees AT yuzhu theboundsoftheedgenumberingeneralizedhypertrees AT liangwei theboundsoftheedgenumberingeneralizedhypertrees AT kezhang boundsoftheedgenumberingeneralizedhypertrees AT haixingzhao boundsoftheedgenumberingeneralizedhypertrees AT zhonglinye boundsoftheedgenumberingeneralizedhypertrees AT yuzhu boundsoftheedgenumberingeneralizedhypertrees AT liangwei boundsoftheedgenumberingeneralizedhypertrees |